Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
| hal.structure.identifier | Microsoft Research Silicon Valley | |
| dc.contributor.author | ABRAHAM, Ittai | |
| hal.structure.identifier | Department of Computer Science and Applied Mathematics [Rehovot] | |
| dc.contributor.author | CHECHIK, Shiri | |
| 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.contributor.editor | ACM | |
| dc.date.accessioned | 2024-04-15T09:44:52Z | |
| dc.date.available | 2024-04-15T09:44:52Z | |
| dc.date.created | 2012 | |
| dc.date.issued | 2012-05 | |
| dc.date.conference | 2012-05 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/197878 | |
| dc.description.abstractEn | This paper considers fully dynamic (1 + ε) distance oracles and (1 + ε) forbidden-set labeling schemes for pla- nar graphs. For a given n-vertex planar graph G with edge weights drawn from [1,M] and parameter ε > 0, our forbidden-set labeling scheme uses labels of length λ = O(ε−1 log2 n log (nM ) * (ε−1 + log n)). Given the labels of two vertices s and t and of a set F of faulty vertices/edges, our scheme approximates the distance between s and t in G \ F with stretch (1 + ε), in O(|F|2λ) time. We then present a general method to transform (1 + ε) forbidden-set labeling schemas into a fully dynamic (1 + ε) distance oracle. Our fully dynamic (1 + ε) distance oracle is of size O(n log n * (ε−1 + log n)) and has O ̃(n1/2) query and update time, both the query and the update time are worst case. This improves on the best previously known (1 + ε) dynamic distance oracle for planar graphs, which has worst case query time O ̃(n2/3) and amortized update time of O ̃(n2/3). Our (1 + ε) forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch (1 + ε). | |
| dc.description.sponsorship | Calculabilité et complexité en distribué - ANR-11-BS02-0014 | |
| dc.language.iso | en | |
| dc.source.title | 44th Annual ACM Symposium on Theory of Computing (STOC) | |
| dc.subject.en | dynamic data-structure | |
| dc.subject.en | planar graphs | |
| dc.subject.en | compact routing | |
| dc.title.en | Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1145/2213977.2214084 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.description.sponsorshipEurope | Experimental UpdateLess Evolutive Routing | |
| bordeaux.page | 1199-1217 | |
| 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 | 44th Annual ACM Symposium on Theory of Computing (STOC) | |
| bordeaux.country | US | |
| bordeaux.title.proceeding | 44th Annual ACM Symposium on Theory of Computing (STOC) | |
| bordeaux.conference.city | New-York | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00725839 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00725839v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=44th%20Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing%20(STOC)&rft.date=2012-05&rft.spage=1199-1217&rft.epage=1199-1217&rft.au=ABRAHAM,%20Ittai&CHECHIK,%20Shiri&GAVOILLE,%20Cyril&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||