On approximate distance labels and routing schemes with affine stretch
Résumé
For every integral parameter $k > 1$, given an unweighted graph $G$, we construct in polynomial time, for each vertex $u$, a distance label $L(u)$ of size $\tO(n^{2/(2k-1)})$. For any $u,v \in G$, given $L(u),L(v)$ we can return in time $O(k)$ an \emph{affine} approximation $\dh(u,v)$ on the distance $d(u,v)$ between $u$ and $v$ in $G$ such that $d(u,v) \le \dh(u,v) \le (2k-2)d(u,v) + 1$. Hence we say that our distance label scheme has affine stretch of $(2k-2)d+1$. For $k=2$ our construction is comparable to the $O(n^{5/3})$ size, $2d+1$ affine stretch of the distance oracle of P\v{a}tra\c{s}cu and Roditty (FOCS~'10), it incurs a $o(\log{n})$ storage overhead while providing the benefits of a distance label. % For any $k>1$, given a restriction of $o(n^{1+1/(k-1)})$ on the total size of the data structure, our construction provides distance labels with affine stretch of $(2k-2)d+1$ which is better than the stretch $(2k-1)d$ scheme of Thorup and Zwick (J. ACM~'05). % Our second contribution is a compact routing scheme with poly-logarithmic addresses that provides affine stretch guarantees. With $\tO(n^{3/(3k-2)})$-bit routing tables we obtain affine stretch of $(4k-6)d+1$, for any $k>1$. % Given a restriction of $o(n^{1/(k-1)})$ on the table size, our routing scheme provides affine stretch which is better than the stretch $(4k-5)d$ routing scheme of Thorup and Zwick (SPAA~'01).