This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
11th International Conference Information Visualization (IV '07)
Geographic Routing on Improved Coordinates
Zurich, Switzerland
July 04-July 06
ISBN: 0-7695-2900-3
Ulrik Brandes, University of Konstanz
Daniel Fleischer, University of Konstanz
We consider routing methods for networks when geographic positions of nodes are available. Instead of using the original geographic coordinates, however, we precompute virtual coordinates using a barycentric layout. Combined with simple geometric routing rules, this greatly reduces the lengths of routes and outperforms algorithms working on the original coordinates. Along with experimental results we proof properties such as guaranteed message delivery and worst-case optimality. Our methods apply to static networks in which short routes are important, but memory for full routing tables is not available and the one-time-precomputation is affordable.
Citation:
Ulrik Brandes, Daniel Fleischer, "Geographic Routing on Improved Coordinates," iv, pp.263-270, 11th International Conference Information Visualization (IV '07), 2007
Usage of this product signifies your acceptance of the Terms of Use.