Mostrar el registro sencillo del ítem

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

hal.structure.identifierMicrosoft Research Silicon Valley
dc.contributor.authorABRAHAM, Ittai
hal.structure.identifierDepartment of Computer Science and Applied Mathematics [Rehovot]
dc.contributor.authorCHECHIK, Shiri
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierInstitut universitaire de France [IUF]
dc.contributor.authorGAVOILLE, Cyril
dc.contributor.editorACM
dc.date.accessioned2024-04-15T09:44:52Z
dc.date.available2024-04-15T09:44:52Z
dc.date.created2012
dc.date.issued2012-05
dc.date.conference2012-05
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197878
dc.description.abstractEnThis 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.sponsorshipCalculabilité et complexité en distribué - ANR-11-BS02-0014
dc.language.isoen
dc.source.title44th Annual ACM Symposium on Theory of Computing (STOC)
dc.subject.endynamic data-structure
dc.subject.enplanar graphs
dc.subject.encompact routing
dc.title.enFully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
dc.typeCommunication dans un congrès
dc.identifier.doi10.1145/2213977.2214084
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.description.sponsorshipEuropeExperimental UpdateLess Evolutive Routing
bordeaux.page1199-1217
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title44th Annual ACM Symposium on Theory of Computing (STOC)
bordeaux.countryUS
bordeaux.title.proceeding44th Annual ACM Symposium on Theory of Computing (STOC)
bordeaux.conference.cityNew-York
bordeaux.peerReviewedoui
hal.identifierhal-00725839
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00725839v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem