TY - GEN
T1 - Faster approximate diameter and distance oracles in planar graphs
AU - Chan, Timothy M.
AU - Skrepetos, Dimitrios
N1 - Publisher Copyright:
© Timothy M. Chan and Dimitrios Skrepetos.
PY - 2017/9/1
Y1 - 2017/9/1
N2 - We present an algorithm that computes a (1 +ϵ)-Approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O ( n log n ( log n + (1/ ϵ)5)) expected time, improving upon the O ( n ( (1/ ϵ)4 log4 n + 2O(1/ϵ))) -Time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/ ϵ with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion. Moreover, using similar techniques, we improve the (1 + ")-Approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/ ϵ on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time.
AB - We present an algorithm that computes a (1 +ϵ)-Approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O ( n log n ( log n + (1/ ϵ)5)) expected time, improving upon the O ( n ( (1/ ϵ)4 log4 n + 2O(1/ϵ))) -Time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/ ϵ with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion. Moreover, using similar techniques, we improve the (1 + ")-Approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/ ϵ on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time.
KW - Abstract voronoi diagrams
KW - Diameter
KW - Planar graphs
UR - https://www.scopus.com/pages/publications/85030530328
UR - https://www.scopus.com/pages/publications/85030530328#tab=citedBy
U2 - 10.4230/LIPIcs.ESA.2017.25
DO - 10.4230/LIPIcs.ESA.2017.25
M3 - Conference contribution
AN - SCOPUS:85030530328
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 25th European Symposium on Algorithms, ESA 2017
A2 - Sohler, Christian
A2 - Sohler, Christian
A2 - Pruhs, Kirk
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 25th European Symposium on Algorithms, ESA 2017
Y2 - 4 September 2017 through 6 September 2017
ER -