๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Compact Routing with Minimum Stretch

โœ Scribed by Lenore J Cowen


Book ID
102573674
Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
111 KB
Volume
38
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis


We present the first universal compact routing algorithm with maximum stretch bounded by 3 that uses sublinear space at every vertex.The algorithm uses local routing tables of size O(n2j3 log413 n) and achieves paths that are most 3 times the length of the shortest path distances for all nodes in an arbitrary weighted undirected network.This answers an open question of Gavoille and Gengler who showed that any universal compact routing algorithm with maximum stretch strictly less than 3 must use Q(n) local space at some vertex.


๐Ÿ“œ SIMILAR VOLUMES


Compact name-independent routing with mi
โœ Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› Association for Computing Machinery ๐ŸŒ English โš– 130 KB
Compact Routing with Name Independence
โœ Arias, Marta; Cowen, Lenore J.; Laing, Kofi A.; Rajaraman, Rajmohan; Taka, Orjet ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 303 KB