LIPIcs.ISAAC.2021.23.pdf
- Filesize: 1.15 MB
- 14 pages
Document
Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs
Authors
Viktor Fredslund-Hansen 
,
Christian Wulff-Nilsen
-
Part of:
Volume:
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-11-30
File
Document Identifiers
Author Details
Acknowledgements
We are grateful for the thorough and useful feedback provided by the reviewers.
Cite AsGet BibTex
Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen. Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.23
https://doi.org/10.4230/LIPIcs.ISAAC.2021.23
Abstract
Given an undirected n-vertex planar graph G = (V,E,ω) with non-negative edge weight function ω:E → ℝ and given an assigned label to each vertex, a vertex-labeled distance oracle is a data structure which for any query consisting of a vertex u and a label λ reports the shortest path distance from u to the nearest vertex with label λ. We show that if there is a distance oracle for undirected n-vertex planar graphs with non-negative edge weights using s(n) space and with query time q(n), then there is a vertex-labeled distance oracle with Õ(s(n)) space and Õ(q(n)) query time. Using the state-of-the-art distance oracle of Long and Pettie [Long and Pettie, 2021], our construction produces a vertex-labeled distance oracle using n^{1+o(1)} space and query time Õ(1) at one extreme, Õ(n) space and n^o(1) query time at the other extreme, as well as such oracles for the full tradeoff between space and query time obtained in their paper. This is the first non-trivial exact vertex-labeled distance oracle for planar graphs and, to our knowledge, for any interesting graph class other than trees.
Subject Classification
ACM Subject Classification
- Theory of computation → Data structures design and analysis
- Theory of computation → Shortest paths
- Mathematics of computing → Graph algorithms
Keywords
- distance oracle
- vertex labels
- color distance oracle
- planar graph
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, October 2005. URL: https://doi.org/10.1145/1103963.1103966.
- Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Almost optimal distance oracles for planar graphs. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 138-151, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316316.
-
Shiri Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012, pages 325-336, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
- H. Davenport and A. Schinzel. A Combinatorial Problem Connected with Differential Equations. American Journal of Mathematics, 87(3):684, July 1965. URL: https://doi.org/10.2307/2373068.
- James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989. URL: https://doi.org/10.1016/0022-0000(89)90034-2.
- Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren. Holiest minimum-cost paths and flows in surface graphs. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1319-1332. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188904.
-
Paweł Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. Better tradeoffs for exact distance oracles in planar graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 515-529, USA, 2018. Society for Industrial and Applied Mathematics.
- Paweł Gawrychowski, Gad M. Landau, Shay Mozes, and Oren Weimann. The nearest colored node in a tree. Theoretical Computer Science, 710:66-73, 2018. URL: https://doi.org/10.1016/j.tcs.2017.08.021.
-
Danny Hermelin, Avivit Levy, Oren Weimann, and Raphael Yuster. Distance oracles for vertex-labeled graphs. In Luca Aceto, Monika Henzinger, and Jiří Sgall, editors, Automata, Languages and Programming, pages 490-501, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
-
Philip Klein. Multiple-source shortest paths in planar graphs. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pages 146-155, January 2005.
-
Mingfei Li, Chu Chung Christopher Ma, and Li Ning. (1+ε)-distance oracles for vertex-labeled planar graphs. In T-H. Hubert Chan, Lap Chi Lau, and Luca Trevisan, editors, Theory and Applications of Models of Computation, pages 42-51, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
- Yaowei Long and Seth Pettie. Planar Distance Oracles with Better Time-Space Tradeoffs. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2517-2537. Society for Industrial and Applied Mathematics, Philadelphia, PA, January 2021. URL: https://doi.org/10.1137/1.9781611976465.149.
- Shay Mozes and Eyal E. Skop. Efficient Vertex-Label Distance Oracles for Planar Graphs. Theory of Computing Systems, 62(2):419-440, February 2018. URL: https://doi.org/10.1007/s00224-017-9827-0.
- Maximilian Probst. On the Complexity of the (Approximate) Nearest Colored Node Problem. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1-68:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.68.
- Dekel Tsur. Succinct data structures for nearest colored node in a tree. Information Processing Letters, 132:6-10, 2018. URL: https://doi.org/10.1016/j.ipl.2017.10.001.