Compact Roundtrip Routing for Digraphs

The first sublinear space universal compact routing schemes for directed graphs are presented. The first scheme uses O( p n log 2 n)-sized routing tables on average at each node, and the second achieves O(n 2=3 log 4=3 n)-sized routing tables maximum space at every node. Both schemes use O(logn) bit vertex addresses and achieve roundtrip routes of stretch at most 3 compared to the optimal roundtrip shortest paths in any strongly connected weighted or unweighted digraph. 1 Introduction The approximate shortest path problem is concerned with computing short routes between pairs of nodes in a network faster than the time it would take to find the shortest paths exactly, although the length of the route may be longer that the shortest path between the nodes. The compact routing problem instead considers a tradeoff of route lengths for space, in the setting where each node locally stores its own routing tables. Much recent work has been done on fast constructions of approximate sh..