Abstract
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 language | English |
|---|---|
| Title of host publication | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 |
| Editors | Hee-Kap Ahn, Kunihiko Sadakane |
| Number of pages | 12 |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publication date | 2021 |
| Article number | 25 |
| ISBN (Electronic) | 9783959772143 |
| DOIs | |
| Publication status | Published - 2021 |
| Event | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan Duration: 6 Dec 2021 → 8 Dec 2021 |
Conference
| Conference | 32nd International Symposium on Algorithms and Computation, ISAAC 2021 |
|---|---|
| Country/Territory | Japan |
| City | Fukuoka |
| Period | 06/12/2021 → 08/12/2021 |
| Series | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 212 |
| ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:© Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen.
Keywords
- Distance oracle
- Planar graph
- Shortest paths
- Subquadratic