TITLE: Approximate Distance Labeling Schemes
(Extended abstract)
AUTHORS: Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul and David Peleg
ABSTRACT:
We consider the problem of labeling the nodes of an n-node
graph G with short labels in such a way that the distance
between any two nodes u,v of G can be approximated
efficiently (in constant time) by merely inspecting the labels of
u and v, without using any other information. We
develop such constant approximate distance labeling schemes for the
classes of trees, bounded treewidth graphs, planar graphs,
k-chordal graphs, and graphs with a dominating pair (including
for instance interval, permutation, and AT-free graphs). We also
establish lower bounds, and prove that most of our schemes are optimal
in terms of the length of the labels generated and the quality of the
approximation.