labeling schemes for flow and connectivity
This paper studies labeling schemes for flow and connectivity functions. A flow labeling scheme using O (log n ? log ? )-bit labels is presented for general n -vertex graphs with maximum (integral) capacity ? . This is shown to be asymptotically optimal. For edge-connectivity, this yields a tight bound of ?(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 ?( k log n ) is established for k -vertex connectivity on n -vertex graphs where k is polylogarithmic in n.
label scheme flow connection paper log general graph integrability capacities optimality lower bound