On approximate distance labels and routing schemes with affine stretch
| hal.structure.identifier | Microsoft Research Silicon Valley | |
| dc.contributor.author | ABRAHAM, Ittai | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Institut universitaire de France [IUF] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| dc.date.accessioned | 2024-04-15T09:46:19Z | |
| dc.date.available | 2024-04-15T09:46:19Z | |
| dc.date.issued | 2011 | |
| dc.date.conference | 2011-09 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197994 | |
| dc.description.abstractEn | 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). | |
| dc.language.iso | en | |
| dc.publisher | Springer | |
| dc.source.title | $25^{th}$ International Symposium on Distributed Computing (DISC) | |
| dc.subject.en | near shortest-path | |
| dc.subject.en | compact data-structures | |
| dc.subject.en | labeling schemes | |
| dc.subject.en | routing schemes | |
| dc.title.en | On approximate distance labels and routing schemes with affine stretch | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-642-24100-0_39 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.page | 404-415 | |
| bordeaux.volume | 6950 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | $25^{th}$ International Symposium on Distributed Computing (DISC) | |
| bordeaux.country | IT | |
| bordeaux.title.proceeding | $25^{th}$ International Symposium on Distributed Computing (DISC) | |
| bordeaux.conference.city | Rome | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00651833 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00651833v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=$25%5E%7Bth%7D$%20International%20Symposium%20on%20Distributed%20Computing%20(DISC)&rft.date=2011&rft.volume=6950&rft.spage=404-415&rft.epage=404-415&rft.au=ABRAHAM,%20Ittai&GAVOILLE,%20Cyril&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||