An Optimal Labeling for Node Connectivity.
Journal
Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings
Pages
303-310
Date Issued
2009
Author(s)
Hsu, Tai-Hsin
HSUEH-I LU
Abstract
Given an n-node undirected simple graph G and a positive integer k, the k-connectivity labeling problem for G seeks short labels for the nodes of G such that whether any two nodes are k-connected in G can be determined merely by their labels. For k=1, an optimal solution to the problem is to give each node in the same connected component of G a common log 2 n-bit label, uniquely chosen for this connected component. For k≥2, Katz, Katz, Korman, and Peleg gave the first nontrivial solution to the problem, requiring O(2 k logn) bits per node. The best previously known solution, due to Korman, requires O(k 2logn) bits per node. We give the first asymptotically optimal solution to the problem, requiring only bits per node, which matches a lower bound Ω(klogn) proved by Katz, Katz, Korman, and Peleg. © 2009 Springer-Verlag Berlin Heidelberg.
Type
conference paper