ICS 269, Winter 1999: Theory Seminar
12 February 1999:
Compact Routing with Minimum Stretch
Yi Cao, ICS, UC Irvine
Abstract: The paper presents 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(n2/3log4/3n) 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 W(n)
local space at some vertex.