ABRAHAM, Ittai; GAVOILLE, Cyril

doi:10.1007/978-3-642-24100-0_39

Métadonnées

Licence d’utilisation du document

ABRAHAM, Ittai
Microsoft Research Silicon Valley

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]

Langue

Communication dans un congrès

Ce document a été publié dans

$25^{th}$ International Symposium on Distributed Computing (DISC), $25^{th}$ International Symposium on Distributed Computing (DISC), $25^{th}$ International Symposium on Distributed Computing (DISC), 2011-09, Rome. 2011, vol. 6950, p. 404-415

Springer

Résumé en anglais

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).< Réduire

Mots clés en anglais

near shortest-path

compact data-structures

labeling schemes

routing schemes

Métadonnées

Partager cette publication !

Licence d’utilisation du document

On approximate distance labels and routing schemes with affine stretch

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche