Compact Routing on Euclidian Metrics
- I. Abraham ,
- Dahlia Malkhi
Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004) |
We consider the problem of designing a compact communication network that supports efficient routing in an Euclidean plane. Our network design and routing scheme achieves 1 + stretch, logarithmic diameter, and constant out degree. This improves upon the best known result so far that requires a logarithmic out-degree. Furthermore, our scheme is asymptotically optimal in Euclidean metrics whose diameter is polynomial.