Technical Reports
Display by Author: A
 B
 C
 D
 E
 F
 G
 H
 I
 J
 K
 L
 M
 N
 O
 P
 Q
 R
 S
 T
 U
 V
 W
 X
 Y
 Z
TR20032
NameIndependent Compact Routing in Trees 

Authors:  Laing, Ambrose K. 
Date:  2003 
Pages:  9 
Download Formats:  [PDF] 
Given an undirected graph with positive edge weights, define for each node to be the set of nodes closest to (including itself and breaking ties by node ID). It is shown that the nodes of any tree can be colored with one color per node drawn from a set of colors, so that, for each node , each color appears exactly once in (but for arbitrary graphs, verifying whether they can be similarly colored for constant is NPComplete). As an application of the first result, we present a generalized tradeoff scheme that, for any fixed constant and any , uses space , headers of length , makes intermediate routing decisions in time, and achieves stretch . For fixed , this realizes sized headers when we choose . A singlesource compact routing tradeoff scheme achieves the a stretch of with the same space and header constraints. Our schemes use underlying optimal namedependent tree routing algorithms from from Thorup and Zwick, and from Fraigniaud and Gavoille. 
Faculty: for help posting a technical report please visit the User Guide.