Standard
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. / Fredslund-Hansen, Viktor; Mozes, Shay; Wulff-Nilsen, Christian.
32nd International Symposium on Algorithms and Computation, ISAAC 2021. ed. / Hee-Kap Ahn; Kunihiko Sadakane. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 25 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 212).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Fredslund-Hansen, V, Mozes, S
& Wulff-Nilsen, C 2021,
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. in H-K Ahn & K Sadakane (eds),
32nd International Symposium on Algorithms and Computation, ISAAC 2021., 25, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 212, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, Fukuoka, Japan,
06/12/2021.
https://doi.org/10.4230/LIPIcs.ISAAC.2021.25APA
Fredslund-Hansen, V., Mozes, S.
, & Wulff-Nilsen, C. (2021).
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. In H-K. Ahn, & K. Sadakane (Eds.),
32nd International Symposium on Algorithms and Computation, ISAAC 2021 [25] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 212
https://doi.org/10.4230/LIPIcs.ISAAC.2021.25Vancouver
Fredslund-Hansen V, Mozes S
, Wulff-Nilsen C.
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. In Ahn H-K, Sadakane K, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2021. 25. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 212).
https://doi.org/10.4230/LIPIcs.ISAAC.2021.25Author
Fredslund-Hansen, Viktor ; Mozes, Shay ; Wulff-Nilsen, Christian. / Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs. 32nd International Symposium on Algorithms and Computation, ISAAC 2021. editor / Hee-Kap Ahn ; Kunihiko Sadakane. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 212).
Bibtex
@inproceedings{ba4c658309b049ddb448cf6b56d0449f,
title = "Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs",
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.",
keywords = "Distance oracle, Planar graph, Shortest paths, Subquadratic",
author = "Viktor Fredslund-Hansen and Shay Mozes and Christian Wulff-Nilsen",
note = "Publisher Copyright: {\textcopyright} Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen.; 32nd International Symposium on Algorithms and Computation, ISAAC 2021 ; Conference date: 06-12-2021 Through 08-12-2021",
year = "2021",
doi = "10.4230/LIPIcs.ISAAC.2021.25",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Hee-Kap Ahn and Kunihiko Sadakane",
booktitle = "32nd International Symposium on Algorithms and Computation, ISAAC 2021",
}
RIS
TY - GEN
T1 - Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs
AU - Fredslund-Hansen, Viktor
AU - Mozes, Shay
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright:
© Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Distance oracle
KW - Planar graph
KW - Shortest paths
KW - Subquadratic
UR - http://www.scopus.com/inward/record.url?scp=85122458758&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2021.25
DO - 10.4230/LIPIcs.ISAAC.2021.25
M3 - Article in proceedings
AN - SCOPUS:85122458758
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd International Symposium on Algorithms and Computation, ISAAC 2021
A2 - Ahn, Hee-Kap
A2 - Sadakane, Kunihiko
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd International Symposium on Algorithms and Computation, ISAAC 2021
Y2 - 6 December 2021 through 8 December 2021
ER -
