Labeling Schemes for Flow and Connectivity
Michal Tzuchman Katz, Nir A. Katz, Amos Korman, David Peleg · SIAM Journal on Computing · 2004
This paper studies labeling schemes for flow and connectivity functions. A flow labeling scheme using $O(\log n\cdot\log {\hat{\omega}}+\log^2n)$-bit labels is presented for general n-vertex graphs with maximum (integral) capacity ${\hat{\omega}}$. This is shown to be asymptotically optimal. For edge-connectivity, this yields a tight bound of $\Theta(\log^2 n)$ bits. A k-vertex connectivity labeling scheme is then given for general n-vertex graphs using at most 3 log n bits for k = 2, 5 log n bits for k = 3, and 2 k log n bits for k > 3. Finally, a lower bound of $\Omega (k\log n)$ is established for k -vertex connectivity on n-vertex graphs, where k is polylogarithmic in n.