Labeling schemes for flow and connectivity
Labeling schemes for flow and connectivity
复制标题
流量和连通性的标签方案
DOI：
10.1137/s0097539703433912
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Michal Katz;Nir A. Katz;Amos Korman;D. Peleg
本文研究了流函数和连通性函数的标注方案。对于最大（积分）容量<i> </i>的一般<i>n</i>顶点图，提出了一种使用<i>O</i>(log <i>n</i> log <i> </i>)位标记的流标记方案。这被证明是渐近最优的。对于边连接，这会产生Θ（log<sup>2</sup> <i>n</i>）位的紧密边界。对于一般<i>n</i>-顶点图，给出了一个<i>k</i>-顶点连通性标记方案，使用最多3个log <i>n</i>位<i>k</i> = 2,5个log <i>n</i>位<i>k</i> = 3和2个<sup><i>k</i></sup> log <i>n</i>位<i>k</i> > 3。最后，对于<i>k</i>-顶点图在<i>n</i>-顶点图上的连通性，建立了Ω的下界（<i>k</i> log <i>n</i>），其中<i>k</i>在<i>n.</i>中是多对数的
This paper studies labeling schemes for flow and connectivity functions. A flow labeling scheme using <i>O</i>(log <i>n</i> ṡ log <i>ŵ</i>)-bit labels is presented for general <i>n</i>-vertex graphs with maximum (integral) capacity <i>ŵ</i>. This is shown to be asymptotically optimal. For edge-connectivity, this yields a tight bound of Θ(log<sup>2</sup> <i>n</i>) bits. A <i>k</i>-vertex connectivity labeling scheme is then given for general <i>n</i>-vertex graphs using at most 3 log <i>n</i> bits for <i>k</i> = 2, 5 log <i>n</i> bits for <i>k</i> = 3 and 2<sup><i>k</i></sup> log <i>n</i> bits for <i>k</i> > 3. Finally, a lower bound of Ω(<i>k</i> log <i>n</i>) is established for <i>k</i>-vertex connectivity on <i>n</i>-vertex graphs where <i>k</i> is polylogarithmic in <i>n.</i>