Advertisement
Published in:
2005 | OriginalPaper | Chapter
Compact Routing for Graphs Excluding a Fixed Minor
Extended Abstract
Authors : Ittai Abraham, Cyril Gavoille, Dahlia Malkhi
Published in: Distributed Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper concerns compact routing schemes with arbitrary node names. We present a compact name-independent routing scheme for unweighted networks with
n
nodes excluding a fixed minor. For any fixed minor, the scheme, constructible in polynomial time, has constant stretch factor and requires routing tables with poly-logarithmic number of bits at each node.
For shortest-path labeled routing scheme in planar graphs, we prove an Ω(
n
ε
) space lower bound for some constant
ε
> 0. This lower bound holds even for bounded degree triangulations, and is optimal for polynomially weighted planar graphs (
ε
=1/2).