On approximate distance labels and routing schemes with affine stretch
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]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]
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]
< Leer menos
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]
Idioma
en
Communication dans un congrès
Este ítem está publicado en
$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
Resumen en inglés
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 ...Leer más >
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).< Leer menos
Palabras clave en inglés
near shortest-path
compact data-structures
labeling schemes
routing schemes
Orígen
Importado de HalCentros de investigación