Document Open Access Logo

Improved Bounds for Shortest Paths in Dense Distance Graphs

Authors Pawel Gawrychowski, Adam Karczmarz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.61.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Pawel Gawrychowski
  • Institute of Computer Science, University of Wrocław, Poland
Adam Karczmarz
  • University of Warsaw, Poland

Funding

  • Karczmarz, Adam: Supported by the grants 2014/13/B/ST6/01811 and 2017/24/T/ST6/00036 of the Polish National Science Center.

Cite As Get BibTex

Pawel Gawrychowski and Adam Karczmarz. Improved Bounds for Shortest Paths in Dense Distance Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.61

Abstract

We study the problem of computing shortest paths in so-called dense distance graphs, a basic building block for designing efficient planar graph algorithms. Let G be a plane graph with a distinguished set partial{G} of boundary vertices lying on a constant number of faces of G. A distance clique of G is a complete graph on partial{G} encoding all-pairs distances between these vertices. A dense distance graph is a union of possibly many unrelated distance cliques.
Fakcharoenphol and Rao [Fakcharoenphol and Rao, 2006] proposed an efficient implementation of Dijkstra's algorithm (later called FR-Dijkstra) computing single-source shortest paths in a dense distance graph. Their algorithm spends O(b log^2{n}) time per distance clique with b vertices, even though a clique has b^2 edges. Here, n is the total number of vertices of the dense distance graph. The invention of FR-Dijkstra was instrumental in obtaining such results for planar graphs as nearly-linear time algorithms for multiple-source-multiple-sink maximum flow and dynamic distance oracles with sublinear update and query bounds.
At the heart of FR-Dijkstra lies a data structure updating distance labels and extracting minimum labeled vertices in O(log^2{n}) amortized time per vertex. We show an improved data structure with O((log^2{n})/(log^2 log n)) amortized bounds. This is the first improvement over the data structure of Fakcharoenphol and Rao in more than 15 years. It yields improved bounds for all problems on planar graphs, for which computing shortest paths in dense distance graphs is currently a bottleneck.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • shortest paths
  • dense distance graph
  • planar graph
  • Monge matrix

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195-208, 1987. URL: http://dx.doi.org/10.1007/BF01840359.
  2. Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, and Sharath Raghvendra. A faster algorithm for minimum-cost bipartite perfect matching in planar graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 457-476, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.31.
  3. Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-pairs minimum cuts in near-linear time for surface-embedded graphs. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 22:1-22:16, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.22.
  4. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM J. Comput., 46(4):1280-1303, 2017. URL: http://dx.doi.org/10.1137/15M1042929.
  5. Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen. Min st-cut oracle for planar graphs with near-linear preprocessing time. ACM Trans. Algorithms, 11(3):16:1-16:29, 2015. URL: http://dx.doi.org/10.1145/2684068.
  6. Sergio Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2143-2152, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.139.
  7. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.05.007.
  8. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. URL: http://dx.doi.org/10.1145/28869.28874.
  9. Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n^5/3) time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 495-514, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.33.
  10. Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Submatrix maximum queries in monge matrices are equivalent to predecessor search. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 580-592, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_47.
  11. Paweł Gawrychowski and Adam Karczmarz. Improved bounds for shortest paths in dense distance graphs, 2016. URL: http://arxiv.org/abs/1602.07013.
  12. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 313-322, 2011. URL: http://dx.doi.org/10.1145/1993636.1993679.
  13. Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in monge matrices and partial monge matrices, and their applications. ACM Trans. Algorithms, 13(2):26:1-26:42, 2017. URL: http://dx.doi.org/10.1145/3039873.
  14. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 146-155, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  15. Philip N. Klein and Shay Mozes. Optimization algorithms for planar graphs, 2017. URL: http://planarity.org.
  16. Philip N. Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 505-514, 2013. URL: http://dx.doi.org/10.1145/2488608.2488672.
  17. LackiJakub Łącki, and Piotr Sankowski and. Min-cuts and shortest cycles in planar graphs in o(n loglogn) time. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, pages 155-166, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_14.
  18. LackiJakub Łącki, Yahav Nussbaum, Piotr Sankowski and Christian Wulff-Nilsen. Single source - all sinks max flows in planar digraphs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 599-608, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.66.
  19. Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci., 32(3):265-279, 1986. URL: http://dx.doi.org/10.1016/0022-0000(86)90030-9.
  20. Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, and Oren Weimann. Minimum cut of directed planar graphs in O(n log log n) time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 477-494, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.32.
  21. Shay Mozes, Yahav Nussbaum, and Oren Weimann. Faster shortest paths in dense distance graphs, with applications. Theor. Comput. Sci., 711:11-35, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2017.10.034.
  22. Shay Mozes and Christian Wulff-Nilsen. Shortest paths in planar graphs with real lengths in O(nlog²n/log logn) time. In Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II, pages 206-217, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15781-3_18.
  23. Yahav Nussbaum. Network flow problems in planar graphs. PhD thesis, Tel Aviv University, 2014. Google Scholar
  24. Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett., 6(3):80-82, 1977. URL: http://dx.doi.org/10.1016/0020-0190(77)90031-X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact