# 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). },

}