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

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 826 KB, PDF-dokument

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.

OriginalsprogEngelsk
Titel32nd International Symposium on Algorithms and Computation, ISAAC 2021
RedaktørerHee-Kap Ahn, Kunihiko Sadakane
Antal sider12
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2021
Artikelnummer25
ISBN (Elektronisk)9783959772143
DOI
StatusUdgivet - 2021
Begivenhed32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan
Varighed: 6 dec. 20218 dec. 2021

Konference

Konference32nd International Symposium on Algorithms and Computation, ISAAC 2021
LandJapan
ByFukuoka
Periode06/12/202108/12/2021
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind212
ISSN1868-8969

ID: 291366923