The Compact Routing Problem: Finding Landmarks in Undirected and Directed Networks

Abstract

Suppose you were going to have a yard sale, and you wished to publish directions. Typically, you would select a major street or landmark and publish directions from all points to the landmark, and then careful directions from the landmark to your location. It turns out that this paradigm is also behind many of the best compact routing schemes, where the "directions" or routing information, are stored locally at each node in the network: in the analogy above, this is equivalent to the person having only a short address, and learning directions to his destination from looking at small signs posted at each street corner. We present a labeling algorithm for undirected n-vertex networks that uses "street signs" of size O(n^{2/3} log^{4/3} n), destination addresses of size 3 \log n, and yields routes between any pair of nodes that are never more than 3 times the length of the optimal route. This solves an open problem of Gavoille and Gengler. Recent extensions to directed networks in joint work with Christopher Wagner will also be discussed.