Compact Routing
for Graphs Excluding a Fixed Minor
|
|
|
|
|
Abstract 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). |
||
|
[DISC 05 version pdf] |
||
