Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 826 KB, PDF document

We present a truly subquadratic size distance oracle for reporting, in constant time, the exact shortest-path distance between any pair of vertices of an undirected, unweighted planar graph G. For any ε > 0, our distance oracle requires O(n5/3+ε) space and is capable of answering shortest-path distance queries exactly for any pair of vertices of G in worst-case time O(log(1/ε)). Previously no truly sub-quadratic size distance oracles with constant query time for answering exact shortest paths distance queries existed.

Original languageEnglish
Title of host publication32nd International Symposium on Algorithms and Computation, ISAAC 2021
EditorsHee-Kap Ahn, Kunihiko Sadakane
Number of pages12
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2021
Article number25
ISBN (Electronic)9783959772143
DOIs
Publication statusPublished - 2021
Event32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan
Duration: 6 Dec 20218 Dec 2021

Conference

Conference32nd International Symposium on Algorithms and Computation, ISAAC 2021
LandJapan
ByFukuoka
Periode06/12/202108/12/2021
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume212
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen.

    Research areas

  • Distance oracle, Planar graph, Shortest paths, Subquadratic

ID: 291366923