Close to linear space routing schemes

Let (G=(V,E)) be an unweighted undirected graph with n vertices and m edges, and let (k>2) be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance (varDelta ) from s, routes a message from s to t on a path whose length is (O(kvarDelta +m^{1/k})). The total space used by our routing scheme is (mn^{O(1/sqrt{log n})}), which is almost linear in the number of edges of the graph. We present also a routing scheme with (n^{O(1/sqrt{log n})}) header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every (vin V) is at most (kn^{O(1/sqrt{log n})}deg(v)), where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.