Technical Reports

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 NP-Complete). 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 single-source compact routing tradeoff scheme achieves the a stretch of with the same space and header constraints. Our schemes use underlying optimal name-dependent tree routing algorithms from from Thorup and Zwick, and from Fraigniaud and Gavoille.