Cyril Gavoille and Christian Sommer

SPAA 2011 - 23rd ACM Symposium on Parallelism in Algorithms and Architectures

Routing with *multiplicative* stretch 3
(which means that the path used by the routing scheme can be up to three times longer than a shortest path)
can be done with routing tables of \(\widetilde{\Theta}(n^{1/2})\) bits per node.
The space lower bound is due to the existence of dense graphs with large girth.
Dense graphs can be sparsified to subgraphs, called *spanners*, with various stretch guarantees.
There are spanners with *additive* stretch guarantees (some even have constant additive stretch)
but only very few additive routing schemes are known.

In this paper, we give reasons why routing in unweighted graphs with *additive* stretch is difficult
in the form of space lower bounds for general graphs and for planar graphs.
We prove that any routing scheme with additive stretch \(\beta\)
and addresses of poly-logarithmic length
must use routing tables of size \(\widetilde{\Omega}\left(\frac{n}{\beta^2}\right)\) bits per node for general graphs,
and \(\widetilde{\Omega}\left(\frac{\sqrt{n}}{\beta}\right)\) for planar graphs.
Routing with tables of size \(O(n^{1/3})\) thus requires a polynomial additive stretch of \(\widetilde{\Omega}(n^{1/3})\),
whereas spanners with average degree \(O(n^{1/3})\) and *constant* additive stretch exist for all graphs.
Spanners, however sparse they are, do not tell us how to route.
These bounds provide the first separation of sparse spanner problems and compact routing problems.

On the positive side, we give an almost tight upper bound:
we present the first non-trivial compact routing scheme with \(o(\log^2 n)\)-bit addresses,
*additive* stretch \(\widetilde{O}(n^{1/3})\), and
table size \(\widetilde{O}(n^{1/3})\) bits for all graphs with linear local tree-width
such as planar, bounded-genus, and apex-minor-free graphs.

**Note**: Asymptotic notation in this abstract suppresses factors logarithmic in \(n\).

@inproceedings{GS11, author = {Cyril Gavoille and Christian Sommer}, title = {Sparse Spanners vs. Compact Routing}, booktitle = {23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, year = {2011}, pages = {225--234}, url = {http://dx.doi.org/10.1145/1989493.1989526}, doi = {10.1145/1989493.1989526}, }

Official version

Local version (300.7 KB)

Slides (370.2 KB)

Home → Publications → Sparse Spanners vs. Compact Routing