AbGa11
Summary
Abraham, Ittai and Gavoille, Cyril (2011) On approximate distance labels and routing schemes with affine stretch. In 25th International Symposium on DIStributed Computing (DISC'11). Roma, Italy, sep. Springer, pages 404-415. ((URL)) (PDF)
Abstract
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 {$\tilde{O}(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 {$d_h(u,v)$} on the distance {$d(u,v)$} between {$u$} and {$v$} in {$G$} such that {$d(u,v) \le d_h(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 {$\tilde{O}(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).
Bibtex entry
@INPROCEEDINGS { AbGa11,
AUTHOR = { Abraham, Ittai and Gavoille, Cyril },
TITLE = { On approximate distance labels and routing schemes with affine stretch },
BOOKTITLE = { 25th International Symposium on DIStributed Computing (DISC'11) },
YEAR = { 2011 },
PAGES = { 404-415 },
PUBLISHER = { Springer },
SERIES = { Lecture Notes in Computer Science },
VOLUME = { 6950 },
MONTH = { sep },
ADDRESS = { Roma, Italy },
URL = { http://dx.doi.org/10.1007/978-3-642-24100-0_39 },
PDF = { http://dept-info.labri.fr/~gavoille/article/AG11 },
ABSTRACT = { 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 {$\tilde{O}(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 {$d_h(u,v)$} on the distance {$d(u,v)$} between {$u$} and {$v$} in {$G$} such that {$d(u,v) \le d_h(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 {$\tilde{O}(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). },
}