Compact routing with minimum stretch

We present the first universal compact routing algorithm with maximum stret ch bounded by 3 that uses sublinear space at every vertex. The algorithm us es local routing tables of size O(n(2/3) log(4/3) n) and achieves paths tha t 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 algor ithm with maximum stretch strictly less than 3 must use Omega (n) local spa ce at some vertex (C) 2001 Academic Press.