A note on exact distance labeling

作者：Weimann Oren^*; Peleg David

来源：Information Processing Letters, 2011, 111(14): 671-673.

DOI：10.1016/j.ipl.2011.04.006

• Labeling schemes
• Shortest paths
• Graph algorithms
• Distributed systems

We show that the vertices of an edge-weighted undirected graph can be labeled with labels of size O(n) such that the exact distance between ally two vertices can be inferred from their labels alone in O(log* n) time. This improves the previous best exact distance labeling scheme that also requires O(n)-sized labels but O(log log n) time to compute the distance. Our scheme is almost optimal as exact distance labeling is known to require labels of length Omega(n).

• 出版日期2011-7-31