More Web Proxy on the site http://driver.im/

research-article

Single-source shortest paths and strong connectivity in dynamic planar graphs

Authors:

Panagiotis Charalampopoulos,

Adam KarczmarzAuthors Info & Claims

Volume 124, Issue C

Pages 97 - 111

https://doi.org/10.1016/j.jcss.2021.09.008

Published: 01 March 2022 Publication History

Abstract

We give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with O ˜ ( n 4 / 5 ) worst-case update time and O ( log 2 ⁡ 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. We then extend our approach, obtaining a data structure that can maintain a planar digraph under edge insertions and deletions, and is 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.

References

[1]

P. Charalampopoulos, A. Karczmarz, Single-source shortest paths and strong connectivity in dynamic planar graphs, in: 28th Annual European Symposium on Algorithms, ESA 2020, 2020, https://doi.org/10.4230/LIPIcs.ESA.2020.31.

[2]

C. Demetrescu, G.F. Italiano, A new approach to dynamic all pairs shortest paths, J. ACM 51 (6) (2004) 968–992,.

Digital Library

[3]

M. Thorup, Fully-dynamic all-pairs shortest paths: faster and allowing negative cycles, in: Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Proceedings, 2004, pp. 384–396. https://doi.org/10.1007/978-3-540-27810-8_33.

[4]

D.B. Johnson, Efficient algorithms for shortest paths in sparse networks, J. ACM 24 (1) (1977) 1–13,.

Digital Library

[5]

I. Abraham, S. Chechik, S. 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, 2017, pp. 440–452. https://doi.org/10.1137/1.9781611974782.28.

[6]

M.P. Gutenberg, C. 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, SIAM, 2020, pp. 2562–2574. https://doi.org/10.1137/1.9781611975994.156.

[7]

M. 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, 2005, pp. 112–119. https://doi.org/10.1145/1060590.1060607.

[8]

G. Ausiello, G.F. Italiano, A. Marchetti-Spaccamela, U. Nanni, Incremental algorithms for minimal length paths, in: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 1990, 1990, pp. 12–21. http://dl.acm.org/citation.cfm?id=320176.320178.

[9]

S. Baswana, R. Hariharan, S. Sen, Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths, J. Algorithms 62 (2) (2007) 74–92,.

Digital Library

[10]

J. Evald, V. Fredslund-Hansen, M.P. Gutenberg, C. Wulff-Nilsen, Decremental APSP in unweighted digraphs versus an adaptive adversary, in: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 2021, https://doi.org/10.4230/LIPIcs.ICALP.2021.64.

[11]

S. Even, Y. Shiloach, An on-line edge-deletion problem, J. ACM 28 (1) (1981) 1–4,.

Digital Library

[12]

L. Roditty, U. Zwick, On dynamic shortest paths problems, Algorithmica 61 (2) (2011) 389–401,.

Digital Library

[13]

M.P. Gutenberg, V.V. Williams, N. Wein, New algorithms and hardness for incremental single-source shortest paths in directed graphs, in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, ACM, 2020, pp. 153–166. https://doi.org/10.1145/3357713.3384236.

[14]

A. Bernstein, Maintaining shortest paths under deletions in weighted directed graphs, SIAM J. Comput. 45 (2) (2016) 548–574,.

Digital Library

[15]

Bernstein, A.; van den Brand, J.; Gutenberg, M.P.; Nanongkai, D.; Saranurak, T.; Sidford, A.; Sun, H. : Fully-dynamic graph sparsifiers against an adaptive adversary. CoRR arXiv:2004.08432 [abs].

[16]

A. Bernstein, S. 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, 2016, pp. 389–397. https://doi.org/10.1145/2897518.2897521.

[17]

A. Bernstein, Deterministic partially dynamic single source shortest paths in weighted graphs, in: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, 2017, https://doi.org/10.4230/LIPIcs.ICALP.2017.44.

[18]

A. Bernstein, S. 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, 2017, pp. 453–469. https://doi.org/10.1137/1.9781611974782.29.

[19]

A. Bernstein, M.P. Gutenberg, C. Wulff-Nilsen, Near-optimal decremental SSSP in dense weighted digraphs, in: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 2020, pp. 1112–1122.

[20]

S. Chechik, Near-optimal approximate decremental all pairs shortest paths, in: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, IEEE Computer Society, 2018, pp. 170–181. https://doi.org/10.1109/FOCS.2018.00025.

[21]

J. Chuzhoy, S. 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, ACM, 2019, pp. 389–400. https://doi.org/10.1145/3313276.3316320.

[22]

M.P. Gutenberg, C. 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, SIAM, 2020, pp. 2522–2541. https://doi.org/10.1137/1.9781611975994.154.

[23]

M.P. Gutenberg, C. 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, SIAM, 2020, pp. 2542–2561. https://doi.org/10.1137/1.9781611975994.155.

[24]

M. Henzinger, S. Krinninger, D. Nanongkai, Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs, in: Symposium on Theory of Computing, STOC 2014, 2014, pp. 674–683. https://doi.org/10.1145/2591796.2591869.

[25]

M. Henzinger, S. Krinninger, D. 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, 2014, pp. 146–155. https://doi.org/10.1109/FOCS.2014.24.

[26]

M. Henzinger, S. Krinninger, D. Nanongkai, Dynamic approximate all-pairs shortest paths: breaking the O ( m n ) barrier and derandomization, SIAM J. Comput. 45 (3) (2016) 947–1006,.

Digital Library

[27]

A. Karczmarz, J. Łącki, Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs, in: 27th Annual European Symposium on Algorithms, ESA 2019, 2019, https://doi.org/10.4230/LIPIcs.ESA.2019.65.

[28]

A. Karczmarz, J. Łącki, Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs, in: 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020, SIAM, 2020, pp. 106–120. https://doi.org/10.1137/1.9781611976014.15.

[29]

A. Bernstein, M.P. Gutenberg, T. Saranurak, Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing, in: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 2020, pp. 1123–1134. https://doi.org/10.1109/FOCS46700.2020.00108.

[30]

Bernstein, A.; Gutenberg, M.P.; Saranurak, T. : Deterministic decremental SSSP and approximate min-cost flow in almost-linear time. CoRR arXiv:2101.07149.

[31]

A. Mądry, 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, ACM, 2010, pp. 121–130. https://doi.org/10.1145/1806689.1806708.

[32]

I. Abraham, S. Chechik, C. 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, 2012, pp. 1199–1218. https://doi.org/10.1145/2213977.2214084.

[33]

I. Abraham, S. Chechik, D. Delling, A.V. Goldberg, R.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, 2016, pp. 740–753. https://doi.org/10.1137/1.9781611974331.ch53.

[34]

J. Fakcharoenphol, S. Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, J. Comput. Syst. Sci. 72 (5) (2006) 868–889,.

Digital Library

[35]

H. Kaplan, S. Mozes, Y. Nussbaum, M. Sharir, Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications, ACM Trans. Algorithms 13 (2) (2017),.

Digital Library

[36]

P.N. Klein, Multiple-source shortest paths in planar graphs, in: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005, 2005, pp. 146–155. http://dl.acm.org/citation.cfm?id=1070432.1070454.

[37]

P.N. Klein, S. Subramanian, A fully dynamic approximation scheme for shortest paths in planar graphs, Algorithmica 22 (3) (1998) 235–249,.

[38]

A. 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, SIAM, 2018, pp. 73–92. https://doi.org/10.1137/1.9781611975031.5.

[39]

S. Chechik, Approximate distance oracles with improved bounds, in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, 2015, pp. 1–10. https://doi.org/10.1145/2746539.2746562.

[40]

C. Wulff-Nilsen, Approximate distance oracles with improved query time, in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, SIAM, 2013, pp. 539–549. https://doi.org/10.1137/1.9781611973105.39.

[41]

M. Thorup, U. Zwick, Approximate distance oracles, J. ACM 52 (1) (2005) 1–24,.

Digital Library

[42]

S. Cabello, Many distances in planar graphs, Algorithmica 62 (1–2) (2012) 361–381,.

Digital Library

[43]

D.Z. Chen, J. Xu, Shortest path queries in planar graphs, in: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, 2000, pp. 469–478. https://doi.org/10.1145/335305.335359.

[44]

H. Djidjev, On-line algorithms for shortest path problems on planar digraphs, in: Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96, 1996, pp. 151–165. https://doi.org/10.1007/3-540-62559-3_14.

[45]

S. Mozes, C. Sommer, Exact distance oracles for planar graphs, in: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, 2012, pp. 209–222. https://doi.org/10.1137/1.9781611973099.19.

[46]

Fredslund-Hansen, V.; Mozes, S.; Wulff-Nilsen, C. : Truly subquadratic exact distance oracles with constant query time for planar graphs. CoRR arXiv:2009.14716 [abs].

[47]

Long, Y.; Pettie, S. : Planar distance oracles with better time-space tradeoffs. in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2517–2537 https://doi.org/10.1137/1.9781611976465.149.

[48]

P. Charalampopoulos, P. Gawrychowski, S. Mozes, O. Weimann, Almost optimal distance oracles for planar graphs, in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, 2019, pp. 138–151. https://doi.org/10.1145/3313276.3316316.

[49]

V. Cohen-Addad, S. Dahlgaard, C. Wulff-Nilsen, Fast and compact exact distance oracle for planar graphs, in: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, 2017, pp. 962–973. https://doi.org/10.1109/FOCS.2017.93.

[50]

P. Gawrychowski, S. Mozes, O. Weimann, C. 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, 2018, pp. 515–529. https://doi.org/10.1137/1.9781611975031.34.

[51]

S. Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs, ACM Trans. Algorithms 15 (2) (2019),.

Digital Library

[52]

P.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, 2002, pp. 820–827. http://dl.acm.org/citation.cfm?id=545381.545488.

[53]

M. Thorup, Compact oracles for reachability and approximate distances in planar digraphs, J. ACM 51 (6) (2004) 993–1024,.

Digital Library

[54]

Q. Gu, G. Xu, Constant query time ( 1 + ϵ ) -approximate distance oracle for planar graphs, in: Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings, in: Lecture Notes in Computer Science, vol. 9472, Springer, 2015, pp. 625–636. https://doi.org/10.1007/978-3-662-48971-0_53.

[55]

K. Kawarabayashi, C. Sommer, M. 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, 2013, pp. 550–563. https://doi.org/10.1137/1.9781611973105.40.

[56]

C. 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, SIAM, 2016, pp. 351–362. https://doi.org/10.1137/1.9781611974331.ch26.

[57]

T.M. Chan, D. Skrepetos, Faster approximate diameter and distance oracles in planar graphs, Algorithmica 81 (8) (2019) 3075–3098,.

Digital Library

[58]

P. Charalampopoulos, S. Mozes, B. Tebeka, Exact distance oracles for planar graphs with failing vertices, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 2019, pp. 2110–2123. https://doi.org/10.1137/1.9781611975482.127.

[59]

P. Gawrychowski, A. Karczmarz, Improved bounds for shortest paths in dense distance graphs, in: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, 2018, https://doi.org/10.4230/LIPIcs.ICALP.2018.61.

[60]

G.F. Italiano, Y. Nussbaum, P. Sankowski, C. 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, 2011, pp. 313–322. https://doi.org/10.1145/1993636.1993679.

[61]

A. Abboud, S. Dahlgaard, Popular conjectures as a barrier for dynamic planar graph algorithms, in: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 2016, pp. 477–486. https://doi.org/10.1109/FOCS.2016.58.

[62]

S. 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, 1993, pp. 372–383. https://doi.org/10.1007/3-540-57273-2_72.

[63]

S. Cabello, E.W. Chambers, J. Erickson, Multiple-source shortest paths in embedded graphs, SIAM J. Comput. 42 (4) (2013) 1542–1571,.

Digital Library

[64]

D. Eppstein, Z. Galil, G.F. Italiano, T.H. Spencer, Separator based sparsification. I. Planary testing and minimum spanning trees, J. Comput. Syst. Sci. 52 (1) (1996) 3–27,.

Digital Library

[65]

J. Holm, E. Rotenberg, Fully-dynamic planarity testing in polylogarithmic time, in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, ACM, 2020, pp. 167–180. https://doi.org/10.1145/3357713.3384249.

[66]

K. Diks, P. Sankowski, Dynamic plane transitive closure, in: Algorithms - ESA 2007, 15th Annual European Symposium, Proceedings, 2007, pp. 594–604. https://doi.org/10.1007/978-3-540-75520-3_53.

[67]

D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J.R. Westbrook, M. Yung, Maintenance of a minimum spanning forest in a dynamic plane graph, J. Algorithms 13 (1) (1992) 33–54,.

Digital Library

[68]

G. Borradaile, P.N. Klein, S. Mozes, Y. Nussbaum, C. Wulff-Nilsen, Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time, SIAM J. Comput. 46 (4) (2017) 1280–1303,.

Digital Library

[69]

G. Borradaile, P.N. Klein, An O(n log n) algorithm for maximum st-flow in a directed planar graph, J. ACM 56 (2) (2009),.

Digital Library

[70]

M.A. Bender, J.T. Fineman, S. Gilbert, R.E. Tarjan, A new approach to incremental cycle detection and related problems, ACM Trans. Algorithms 12 (2) (2016),.

Digital Library

[71]

A. Bernstein, M. Probst, C. 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, ACM, 2019, pp. 365–376. https://doi.org/10.1145/3313276.3316335.

[72]

B. Haeupler, T. Kavitha, R. Mathew, S. Sen, R.E. Tarjan, Incremental cycle detection, topological ordering, and strong component maintenance, ACM Trans. Algorithms 8 (1) (2012),.

Digital Library

[73]

G.F. Italiano, A. Karczmarz, J. Łącki, P. Sankowski, Decremental single-source reachability in planar digraphs, in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, ACM, 2017, pp. 1108–1121. https://doi.org/10.1145/3055399.3055480.

[74]

A. Abboud, V.V. Williams, Popular conjectures imply strong lower bounds for dynamic problems, in: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, IEEE Computer Society, 2014, pp. 434–443. https://doi.org/10.1109/FOCS.2014.53.

[75]

J. Holm, K. de Lichtenberg, M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, J. ACM 48 (4) (2001) 723–760,.

Digital Library

[76]

S. Huang, D. Huang, T. Kopelowitz, S. Pettie, Fully dynamic connectivity in O(logn(loglogn)²) amortized expected time, in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, 2017, pp. 510–520. https://doi.org/10.1137/1.9781611974782.32.

[77]

C. Wulff-Nilsen, Faster deterministic fully-dynamic graph connectivity, in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, SIAM, 2013, pp. 1757–1769. https://doi.org/10.1137/1.9781611973105.126.

[78]

B.M. Kapron, V. King, B. Mountjoy, Dynamic graph connectivity in polylogarithmic worst case time, in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, 2013, pp. 1131–1142. https://doi.org/10.1137/1.9781611973105.81.

[79]

Wang, Z. : An improved randomized data structure for dynamic graph connectivity. CoRR arXiv:1510.04590 [abs].

[80]

D. Nanongkai, T. Saranurak, C. Wulff-Nilsen, Dynamic minimum spanning forest with subpolynomial worst-case update time, in: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, IEEE Computer Society, 2017, pp. 950–961. https://doi.org/10.1109/FOCS.2017.92.

[81]

J. Chuzhoy, Y. Gao, J. Li, D. Nanongkai, R. Peng, T. Saranurak, A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond, in: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 2020, pp. 1158–1167. https://doi.org/10.1109/FOCS46700.2020.00111.

[82]

Goranci, G.; Räcke, H.; Saranurak, T.; Tan, Z. : The expander hierarchy and its applications to dynamic graph algorithms. in: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2212–2228 https://doi.org/10.1137/1.9781611976465.132.

[83]

G.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, 1984, pp. 376–382. https://doi.org/10.1145/800057.808703.

[84]

P.N. Klein, S. Mozes, C. Sommer, Structured recursive separator decompositions for planar graphs in linear time, in: Symposium on Theory of Computing Conference, STOC'13, 2013, pp. 505–514. https://doi.org/10.1145/2488608.2488672.

[85]

G. Borradaile, P. Sankowski, C. Wulff-Nilsen, Min st-cut oracle for planar graphs with near-linear preprocessing time, ACM Trans. Algorithms 11 (3) (2015),.

Digital Library

[86]

G.N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput. 16 (6) (1987) 1004–1022,.

Digital Library

[87]

Y. Nussbaum, Network flow problems in planar graphs, Ph.D. thesis Tel Aviv University, 2014.

[88]

J. Erickson, K. Fox, L. 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, 2018, pp. 1319–1332. https://doi.org/10.1145/3188745.3188904.

[89]

P.N. Klein, S. Mozes, O. Weimann, Shortest paths in directed planar graphs with negative lengths: a linear-space O(nlog²n)-time algorithm, ACM Trans. Algorithms 6 (2) (2010),.

Digital Library

[90]

S. Mozes, C. 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, 2010, pp. 206–217. https://doi.org/10.1007/978-3-642-15781-3_18.

Cited By

Charalampopoulos PGawrychowski PLong YMozes SPettie SWeimann OWulff-Nilsen C(2023)Almost Optimal Exact Distance Oracles for Planar GraphsJournal of the ACM10.1145/358047470:2(1-50)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3580474

Index Terms

Single-source shortest paths and strong connectivity in dynamic planar graphs

Index terms have been assigned to the content through auto-classification.

Recommendations

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science

The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-...
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR ...
A Shortest Path Algorithm for Real-Weighted Undirected Graphs

We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 124, Issue C

Mar 2022

234 pages

ISSN:0022-0000

Issue’s Table of Contents

Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Charalampopoulos PGawrychowski PLong YMozes SPettie SWeimann OWulff-Nilsen C(2023)Almost Optimal Exact Distance Oracles for Planar GraphsJournal of the ACM10.1145/358047470:2(1-50)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3580474

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents