Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfæ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.
Originalsprog | Engelsk |
---|---|
Titel | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 |
Redaktører | Hee-Kap Ahn, Kunihiko Sadakane |
Antal sider | 12 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2021 |
Artikelnummer | 25 |
ISBN (Elektronisk) | 9783959772143 |
DOI | |
Status | Udgivet - 2021 |
Begivenhed | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan Varighed: 6 dec. 2021 → 8 dec. 2021 |
Konference
Konference | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 |
---|---|
Land | Japan |
By | Fukuoka |
Periode | 06/12/2021 → 08/12/2021 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 212 |
ISSN | 1868-8969 |
ID: 291366923