ACG12
Summary
Abraham, Ittai, Chechik, Shiri and Gavoille, Cyril (2012) Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels. In {$44^{th}$} Annual ACM Symposium on Theory of Computing (STOC). may. ACM Press, pages 1199-1218. ((URL)) (PDF)
Abstract
This paper considers fully dynamic {$(1+\varepsilon)$} distance oracles and {$(1+\varepsilon)$} forbidden-set labeling schemes for planar graphs. For a given {$n$}-vertex planar graph {$G$} with edge weights drawn from {1,M$} and parameter {$\varepsilon>0$}, our forbidden-set labeling scheme uses labels of length {$\lambda = O({\varepsilon}^{-1}\log^2{n} \log{(nM)} \cdot ({\varepsilon}^{-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\setminus F$} with stretch {$(1+\varepsilon)$}, in {$O(|F|^2 \lambda)$} time. We then present a general method to transform {$(1+\varepsilon)$} forbidden-set labeling schemes into a fully dynamic {$(1+\varepsilon)$} distance oracle. Our fully dynamic {$(1+\varepsilon)$} distance oracle is of size {$O(n \log{n} \cdot ({\varepsilon}^{-1}+\log{n}))$} and has {$\tilde{O}(n^{1/2})$} query and update time, both the query and the update time are worst case. This improves on the best previously known {$(1+\varepsilon)$} dynamic distance oracle for planar graphs, which has worst case query time {$\tilde{O}(n^{2/3})$} and amortized update time of {$\tilde{O}(n^{2/3})$}. Our {$(1+\varepsilon)$} forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch {$(1+\varepsilon)$}.
Bibtex entry
@INPROCEEDINGS { ACG12,
AUTHOR = { Abraham, Ittai and Chechik, Shiri and Gavoille, Cyril },
TITLE = { Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels },
BOOKTITLE = { {$44^{th}$} Annual ACM Symposium on Theory of Computing (STOC) },
PUBLISHER = { ACM Press },
LOCATION = { New York, NY, USA },
MONTH = { may },
YEAR = { 2012 },
PAGES = { 1199-1218 },
URL = { http://dx.doi.org/10.1145/2213977.2214084 },
DOI = { 10.1145/2213977.2214084 },
PDF = { http://dept-info.labri.fr/~gavoille/article/ACG12.pdf },
KEYWORDS = { data-structure, dynamic, planar, compact routing },
ABSTRACT = { This paper considers fully dynamic {$(1+\varepsilon)$} distance oracles and {$(1+\varepsilon)$} forbidden-set labeling schemes for planar graphs. For a given {$n$}-vertex planar graph {$G$} with edge weights drawn from {1,M$} and parameter {$\varepsilon>0$}, our forbidden-set labeling scheme uses labels of length {$\lambda = O({\varepsilon}^{-1}\log^2{n} \log{(nM)} \cdot ({\varepsilon}^{-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\setminus F$} with stretch {$(1+\varepsilon)$}, in {$O(|F|^2 \lambda)$} time. We then present a general method to transform {$(1+\varepsilon)$} forbidden-set labeling schemes into a fully dynamic {$(1+\varepsilon)$} distance oracle. Our fully dynamic {$(1+\varepsilon)$} distance oracle is of size {$O(n \log{n} \cdot ({\varepsilon}^{-1}+\log{n}))$} and has {$\tilde{O}(n^{1/2})$} query and update time, both the query and the update time are worst case. This improves on the best previously known {$(1+\varepsilon)$} dynamic distance oracle for planar graphs, which has worst case query time {$\tilde{O}(n^{2/3})$} and amortized update time of {$\tilde{O}(n^{2/3})$}. Our {$(1+\varepsilon)$} forbidden-set labeling scheme can also be extended into a forbidden-set labeled routing scheme with stretch {$(1+\varepsilon)$}. },
}