ABRAHAM, Ittai; CHECHIK, Shiri; GAVOILLE, Cyril

doi:10.1145/2213977.2214084

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

ABRAHAM, Ittai
Microsoft Research Silicon Valley

CHECHIK, Shiri
Department of Computer Science and Applied Mathematics [Rehovot]

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]

Idioma

Communication dans un congrès

Este ítem está publicado en

44th Annual ACM Symposium on Theory of Computing (STOC), 44th Annual ACM Symposium on Theory of Computing (STOC), 44th Annual ACM Symposium on Theory of Computing (STOC), 2012-05, New-York. 2012-05p. 1199-1217

Resumen en inglés

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 + ε).< Leer menos

Palabras clave en inglés

dynamic data-structure

planar graphs

compact routing

URI

https://oskar-bordeaux.fr/handle/20.500.12278/197878

DOI

http://dx.doi.org/10.1145/2213977.2214084

Proyecto europeo

Experimental UpdateLess Evolutive Routing

Proyecto ANR

Calculabilité et complexité en distribué - ANR-11-BS02-0014

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800