Document Open Access Logo

Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs

Authors Panagiotis Charalampopoulos , Adam Karczmarz

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.31.pdf
  • Filesize: 0.54 MB
  • 23 pages

Document Identifiers

Author Details

Panagiotis Charalampopoulos
  • Department of Informatics, King’s College London, UK
  • Institute of Informatics, University of Warsaw, Poland
Adam Karczmarz
  • Institute of Informatics, University of Warsaw, Poland

Funding

  • Charalampopoulos, Panagiotis: Partially supported by ERC Starting Grant TOTAL under the EU’s Horizon 2020 Research and Innovation Programme (agreement no. 677651).
  • Karczmarz, Adam: Supported by ERC Consolidator Grant 772346 TUgbOAT and the Polish National Science Centre 2018/29/N/ST6/00757 grant.

Cite As Get BibTex

Panagiotis Charalampopoulos and Adam Karczmarz. Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.31

Abstract

Efficient algorithms for computing and processing additively weighted Voronoi diagrams on planar graphs have been instrumental in obtaining several recent breakthrough results, most notably the almost-optimal exact distance oracle for planar graphs [Charalampopoulos et al., STOC'19], and subquadratic algorithms for planar diameter [Cabello, SODA'17, Gawrychowski et al., SODA'18]. In this paper, we show how Voronoi diagrams can be useful in obtaining dynamic planar graph algorithms and apply them to classical problems such as dynamic single-source shortest paths and dynamic strongly connected components.
First, we give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with Õ(n^{4/5}) worst-case update time and O(log² n) query time. Here, a single update can either change the graph by inserting or deleting an edge, or reset the source s of interest. All known non-trivial planarity-exploiting exact dynamic single-source shortest paths algorithms to date had polynomial query time. Further, note that a data structure with strongly sublinear update time capable of answering distance queries between all pairs of vertices in polylogarithmic time would refute the APSP conjecture [Abboud and Dahlgaard, FOCS'16].
Somewhat surprisingly, the Voronoi diagram based approach we take for single-source shortest paths can also be used in the fully dynamic strongly connected components problem. In particular, we obtain a data structure maintaining a planar digraph under edge insertions and deletions, capable of returning the identifier of the strongly connected component of any query vertex. The worst-case update and query time bounds are the same as for our single-source distance oracle. To the best of our knowledge, this is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for an important class of digraphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Shortest paths
Keywords
  • dynamic graph algorithms
  • planar graphs
  • single-source shortest paths
  • strong connectivity

Metrics

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

References

  1. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 477-486, 2016. URL: https://doi.org/10.1109/FOCS.2016.58.
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 434-443. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  3. Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. On dynamic approximate shortest paths for planar graphs with worst-case costs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 740-753, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch53.
  4. Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, pages 1199-1218, 2012. URL: https://doi.org/10.1145/2213977.2214084.
  5. Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 440-452, 2017. URL: https://doi.org/10.1137/1.9781611974782.28.
  6. Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni. Incremental algorithms for minimal length paths. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pages 12-21, 1990. URL: http://dl.acm.org/citation.cfm?id=320176.320178.
  7. Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. J. Algorithms, 62(2):74-92, 2007. URL: https://doi.org/10.1016/j.jalgor.2004.08.004.
  8. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan. A new approach to incremental cycle detection and related problems. ACM Trans. Algorithms, 12(2):14:1-14:22, 2016. URL: https://doi.org/10.1145/2756553.
  9. Aaron Bernstein. Maintaining shortest paths under deletions in weighted directed graphs. SIAM J. Comput., 45(2):548-574, 2016. URL: https://doi.org/10.1137/130938670.
  10. Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 44:1-44:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.44.
  11. Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the o(mn) bound. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 389-397, 2016. URL: https://doi.org/10.1145/2897518.2897521.
  12. Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 453-469, 2017. URL: https://doi.org/10.1137/1.9781611974782.29.
  13. Aaron Bernstein, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. Near-optimal decremental SSSP in dense weighted digraphs. CoRR, abs/2004.04496, 2020. URL: http://arxiv.org/abs/2004.04496.
  14. Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen. Decremental strongly-connected components and single-source reachability in near-linear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 365-376. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316335.
  15. Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR, abs/2004.08432, 2020. URL: http://arxiv.org/abs/2004.08432.
  16. Glencora Borradaile and Philip N. Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM, 56(2):9:1-9:30, 2009. URL: https://doi.org/10.1145/1502793.1502798.
  17. 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: https://doi.org/10.1137/15M1042929.
  18. 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: https://doi.org/10.1145/2684068.
  19. Sergio Cabello. Many distances in planar graphs. Algorithmica, 62(1-2):361-381, 2012. URL: https://doi.org/10.1007/s00453-010-9459-0.
  20. Sergio Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms, 15(2):21:1-21:38, 2019. URL: https://doi.org/10.1145/3218821.
  21. Sergio Cabello, Erin W. Chambers, and Jeff Erickson. Multiple-source shortest paths in embedded graphs. SIAM J. Comput., 42(4):1542-1571, 2013. URL: https://doi.org/10.1137/120864271.
  22. Timothy M. Chan and Dimitrios Skrepetos. Faster approximate diameter and distance oracles in planar graphs. Algorithmica, 81(8):3075-3098, 2019. URL: https://doi.org/10.1007/s00453-019-00570-z.
  23. Panagiotis Charalampopoulos, Pawel 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, 2019. URL: https://doi.org/10.1145/3313276.3316316.
  24. Panagiotis Charalampopoulos, Shay Mozes, and Benjamin Tebeka. Exact distance oracles for planar graphs with failing vertices. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2110-2123, 2019. URL: https://doi.org/10.1137/1.9781611975482.127.
  25. Shiri Chechik. Approximate distance oracles with improved bounds. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 1-10, 2015. URL: https://doi.org/10.1145/2746539.2746562.
  26. Shiri Chechik. Near-optimal approximate decremental all pairs shortest paths. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 170-181. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00025.
  27. Danny Z. Chen and Jinhui Xu. Shortest path queries in planar graphs. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, pages 469-478, 2000. URL: https://doi.org/10.1145/335305.335359.
  28. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs/1910.08025, 2019. URL: http://arxiv.org/abs/1910.08025.
  29. Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 389-400. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316320.
  30. Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. Fast and compact exact distance oracle for planar graphs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 962-973, 2017. URL: https://doi.org/10.1109/FOCS.2017.93.
  31. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. URL: https://doi.org/10.1145/1039488.1039492.
  32. Krzysztof Diks and Piotr Sankowski. Dynamic plane transitive closure. In Algorithms - ESA 2007, 15th Annual European Symposium, Proceedings, pages 594-604, 2007. URL: https://doi.org/10.1007/978-3-540-75520-3_53.
  33. Hristo Djidjev. On-line algorithms for shortest path problems on planar digraphs. In Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96, pages 151-165, 1996. URL: https://doi.org/10.1007/3-540-62559-3_14.
  34. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification. I. Planary testing and minimum spanning trees. J. Comput. Syst. Sci., 52(1):3-27, 1996. URL: https://doi.org/10.1006/jcss.1996.0002.
  35. David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert Endre Tarjan, Jeffery R. Westbrook, and Moti Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms, 13(1):33-54, 1992. URL: https://doi.org/10.1016/0196-6774(92)90004-V.
  36. Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren. Holiest minimum-cost paths and flows in surface graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1319-1332, 2018. URL: https://doi.org/10.1145/3188745.3188904.
  37. Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. J. ACM, 28(1):1-4, 1981. URL: https://doi.org/10.1145/322234.322235.
  38. 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: https://doi.org/10.1016/j.jcss.2005.05.007.
  39. Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004-1022, 1987. URL: https://doi.org/10.1137/0216064.
  40. 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, pages 61:1-61:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.61.
  41. Pawel 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, 2018. URL: https://doi.org/10.1137/1.9781611975031.34.
  42. Qian-Ping Gu and Gengchun Xu. Constant query time (1+ε) -approximate distance oracle for planar graphs. In Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings, volume 9472 of Lecture Notes in Computer Science, pages 625-636. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48971-0_53.
  43. Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 153-166. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384236.
  44. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2542-2561. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.155.
  45. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2522-2541. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.154.
  46. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2562-2574. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.156.
  47. Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan. Incremental cycle detection, topological ordering, and strong component maintenance. ACM Trans. Algorithms, 8(1):3:1-3:33, 2012. URL: https://doi.org/10.1145/2071379.2071382.
  48. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 146-155, 2014. URL: https://doi.org/10.1109/FOCS.2014.24.
  49. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In Symposium on Theory of Computing, STOC 2014, pages 674-683, 2014. URL: https://doi.org/10.1145/2591796.2591869.
  50. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM J. Comput., 45(3):947-1006, 2016. URL: https://doi.org/10.1137/140957299.
  51. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: https://doi.org/10.1145/502090.502095.
  52. Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully dynamic connectivity in O(log n(log log n)^2) amortized expected time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 510-520, 2017. URL: https://doi.org/10.1137/1.9781611974782.32.
  53. Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Piotr Sankowski. Decremental single-source reachability in planar digraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1108-1121. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055480.
  54. 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, pages 313-322, 2011. URL: https://doi.org/10.1145/1993636.1993679.
  55. Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1-13, 1977. URL: https://doi.org/10.1145/321992.321993.
  56. 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: https://doi.org/10.1145/3039873.
  57. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pages 1131-1142, 2013. URL: https://doi.org/10.1137/1.9781611973105.81.
  58. Adam Karczmarz. Decremental transitive closure and shortest paths for planar digraphs and beyond. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 73-92. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.5.
  59. Adam Karczmarz and Jakub Lacki. Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs. In 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020, pages 106-120. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976014.15.
  60. Adam Karczmarz and Jakub Łącki. Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs. In 27th Annual European Symposium on Algorithms, ESA 2019, pages 65:1-65:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.65.
  61. Ken-ichi Kawarabayashi, Christian Sommer, and Mikkel Thorup. More compact oracles for approximate distances in undirected planar graphs. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pages 550-563, 2013. URL: https://doi.org/10.1137/1.9781611973105.40.
  62. Philip N. Klein. Preprocessing an undirected planar network to enable fast approximate distance queries. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms,SODA 2002, pages 820-827, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545488.
  63. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 146-155, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  64. 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, pages 505-514, 2013. URL: https://doi.org/10.1145/2488608.2488672.
  65. Philip N. Klein, Shay Mozes, and Oren Weimann. Shortest paths in directed planar graphs with negative lengths: A linear-space O(nlog²n)-time algorithm. ACM Trans. Algorithms, 6(2):30:1-30:18, 2010. URL: https://doi.org/10.1145/1721837.1721846.
  66. Philip N. Klein and Sairam Subramanian. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica, 22(3):235-249, 1998. URL: https://doi.org/10.1007/PL00009223.
  67. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pages 121-130. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806708.
  68. Gary L. Miller. Finding small simple cycle separators for 2-connected planar graphs. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984, pages 376-382, 1984. URL: https://doi.org/10.1145/800057.808703.
  69. Shay Mozes and Christian Sommer. Exact distance oracles for planar graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pages 209-222, 2012. URL: https://doi.org/10.1137/1.9781611973099.19.
  70. Shay Mozes and Christian Wulff-Nilsen. Shortest paths in planar graphs with real lengths in O(nlog²n/loglogn) time. In Algorithms - ESA 2010, 18th Annual European Symposium. Proceedings, Part II, pages 206-217, 2010. URL: https://doi.org/10.1007/978-3-642-15781-3_18.
  71. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 950-961. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.92.
  72. Yahav Nussbaum. Network flow problems in planar graphs. PhD thesis, Tel Aviv University, 2014. Google Scholar
  73. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  74. Piotr Sankowski. Subquadratic algorithm for dynamic shortest distances. In Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Proceedings, pages 461-470, 2005. URL: https://doi.org/10.1007/11533719_47.
  75. Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30 - October 2, 1993, Proceedings, pages 372-383, 1993. URL: https://doi.org/10.1007/3-540-57273-2_72.
  76. Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. URL: https://doi.org/10.1145/1039488.1039493.
  77. Mikkel Thorup. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Proceedings, pages 384-396, 2004. URL: https://doi.org/10.1007/978-3-540-27810-8_33.
  78. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pages 112-119, 2005. URL: https://doi.org/10.1145/1060590.1060607.
  79. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: https://doi.org/10.1145/1044731.1044732.
  80. Jan van den Brand and Danupon Nanongkai. Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 436-455. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00035.
  81. Zhengyu Wang. An improved randomized data structure for dynamic graph connectivity. CoRR, abs/1510.04590, 2015. URL: http://arxiv.org/abs/1510.04590.
  82. Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pages 539-549. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.39.
  83. Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pages 1757-1769. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.126.
  84. Christian Wulff-Nilsen. Approximate distance oracles for planar graphs with improved query time-space tradeoff. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pages 351-362. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch26.
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