Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $tilde O(frac{1}{epsilon} n^{2/3})$ space at each vertex and $tilde O(1/epsilon)$-bit headers, to route a message between any pair of vertices $u,vin V$ on a $(2 + epsilon,1)$-stretch path, i.e., a path of length at most $(2+epsilon)cdot d(u,v)+1$. This should be compared to the $(2,1)$-stretch and $tilde O(n^{5/3})$ space distance oracle of Patrascu and Roditty [FOCS10 and SIAM J. Comput. 2014] and to the $(2,1)$-stretch routing scheme of Abraham and Gavoille [DISC11] that uses $tilde O( n^{3/4})$ space at each vertex. - A routing scheme for weighted graphs with normalized diameter $D$, that uses $tilde O(frac{1}{epsilon} n^{1/3}log D)$ space at each vertex and $tilde O(frac{1}{epsilon}log D)$-bit headers, to route a message between any pair of vertices on a $(5+epsilon)$-stretch path. This should be compared to the $5$-stretch and $tilde O(n^{4/3})$ space distance oracle of Thorup and Zwick [STOC01 and J. ACM. 2005] and to the $7$-stretch routing scheme of Thorup and Zwick [SPAA01] that uses $tilde O( n^{1/3})$ space at each vertex. Since a $5$-stretch routing scheme must use tables of $Omega( n^{1/3})$ space our result is almost tight. - For an integer $ell>1$, a routing scheme for unweighted graphs that uses $tilde O(ellfrac{1}{epsilon} n^{ell/(2ell pm 1)})$ space at each vertex and $tilde O(frac{1}{epsilon})$-bit headers, to route a message between any pair of vertices on a $(3pm2/ell+epsilon,2)$-stretch path. - A routing scheme for weighted graphs, that uses $tilde O(frac{1}{epsilon}n^{1/k}log D)$ space at each vertex and $tilde O(frac{1}{epsilon}log D)$-bit headers, to route a message between any pair of vertices on a $(4k-7+epsilon)$-stretch path.
Download