Compact routing with additive stretch using distance labelings

ABSTRACT

Distance labelings -- introduced as a new way to encode graph topology in a distributed fashion -- have been an active area of research (see [1, 2] for details). In both exact and approximate settings, results in distance labelings and compact routing (for an introduction, esp. for definitions of routing tables and headers, see [3]) seem to go hand in hand, but so far these results have been produced separately. It was already known that graphs with constantsized separators such as trees, outerplanar graphs, seriesparallel graphs and graphs of bounded treewidth, support both exact distance labelings and optimal (additive stretch 0, multiplicative stretch 1) compact routing schemes, but there are classes of graphs known to admit exact distance labelings which do not have constant-sized separators. Our main result is to demonstrate that every n-vertex graph which supports an exact distance labeling with O(l(n))-sized labels also supports a compact routing scheme with O(l(n) + log² n)-sized headers, O(√n(l(n) + log² n))-sized routing tables, and an additive stretch of 6. Our general result produces the first known compact routing schemes for classes of graphs where no previous compact routing scheme was known, such as permutation graphs.We note that it is possible to improve substantially on our general result for the classes of interval graphs and circular arc graphs (neither of which admits constant-sized separators). In both cases, a compact routing scheme exists with polylogarithmic headers and routing tables, and an additive stretch of 1; due to space constraints, we defer further discussion of these cases to future presentations of this work.

REFERENCES

• 1: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004 [doi>10.1016/j.jalgor.2004.05.002]
• 2: D. Peleg, Proximity-Preserving Labeling Schemes, Weizmann Science Press of Israel, Jerusalem, Israel, 1997
• 3: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms

Keywords:
compact routing