A note on exact distance labeling
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). (C) 2011 Elsevier B.V. All rights reserved.
labeling schemes shortest paths graph algorithms distributed systems