Open AccessCompact routing on euclidian metrics
Author(s) -
Ittai Abraham,
Dahlia Malkhi
Publication year - 2004
Publication title -
citeseer x (the pennsylvania state university)
Language(s) - English
Resource type - Conference proceedings
ISBN - 1-58113-802-4
DOI - 10.1145/1011767.1011789
Subject(s) - logarithm , routing (electronic design automation) , euclidean geometry , euclidean distance , degree (music) , constant (computer programming) , computer science , scheme (mathematics) , polynomial , plane (geometry) , euclidean distance matrix , mathematics , destination sequenced distance vector routing , topology (electrical circuits) , mathematical optimization , link state routing protocol , combinatorics , routing protocol , computer network , mathematical analysis , geometry , physics , artificial intelligence , acoustics , programming language
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom