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
• DOI: 10.1006/jagm.2000.1134

✦ 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.