Labeling schemes for vertex connectivity
Amos Korman · ACM Transactions on Algorithms · 2010
This article studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of assigning short labels to the nodes of any n -node graph is such a way that given the labels of any two nodes u and v , one can decide whether u and v are k -vertex connected in G , that is, whether there exist k vertex disjoint paths connecting u and v . This article establishes an upper bound of k 2 log n on the number of bits used in a label. The best previous upper bound for the label size of such a labeling scheme is 2 k log n .