Compact Name-Independent Routing with Minimum Stretch
- Ittai Abraham ,
- Cyril Gavoille ,
- Dahlia Malkhi ,
- Noam Nisan ,
- Mikkel Thorup
ACM Transactions on Algorithms | , Vol 4: pp. 1-12
Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a e O(√n) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the shortest 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.