Compact name-independent routing with minimum stretch
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup · ACM Transactions on Algorithms · 2008
Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a Õ (√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using o ( n ) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√ n ,)space per node.