Faster approximate diameter and distance oracles in planar graphs

Timothy M. Chan, Dimitrios Skrepetos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication25th European Symposium on Algorithms, ESA 2017
EditorsChristian Sohler, Christian Sohler, Kirk Pruhs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770491
DOIs
StatePublished - Sep 1 2017
Event25th European Symposium on Algorithms, ESA 2017 - Vienna, Austria
Duration: Sep 4 2017Sep 6 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume87
ISSN (Print)1868-8969

Other

Other25th European Symposium on Algorithms, ESA 2017
Country/TerritoryAustria
CityVienna
Period9/4/179/6/17

Keywords

  • Abstract voronoi diagrams
  • Diameter
  • Planar graphs

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Faster approximate diameter and distance oracles in planar graphs'. Together they form a unique fingerprint.

Cite this