ABRAHAM, Ittai; CHECHIK, Shiri; GAVOILLE, Cyril

doi:10.1145/2213977.2214084

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

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]

Langue

Communication dans un congrès

Ce document a été publié dans

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

Résumé en anglais

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 + ε).< Réduire

Mots clés en anglais

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

Projet Européen

Experimental UpdateLess Evolutive Routing

Project ANR

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

Origine

Importé de hal

Unités de recherche

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