{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T23:21:21Z","timestamp":1783984881132,"version":"3.55.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,3,3]],"date-time":"2010-03-03T00:00:00Z","timestamp":1267574400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s00453-010-9401-5","type":"journal-article","created":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T23:15:26Z","timestamp":1267485326000},"page":"389-401","source":"Crossref","is-referenced-by-count":64,"title":["On Dynamic Shortest Paths Problems"],"prefix":"10.1007","volume":"61","author":[{"given":"Liam","family":"Roditty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,3]]},"reference":[{"key":"9401_CR1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9401_CR2","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S. Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"9401_CR3","unstructured":"Baswana, S., Hariharan, R., Sen, S.: Maintaining all-pairs approximate shortest paths under deletion of edges. In: Proc. of 14th SODA, pp.\u00a0394\u2013403 (2003)"},{"issue":"2","key":"9401_CR4","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.jalgor.2004.08.004","volume":"62","author":"S. Baswana","year":"2007","unstructured":"Baswana, S., Hariharan, R., Sen, S.: Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. J. Algorithms 62(2), 74\u201392 (2007)","journal-title":"J. Algorithms"},{"key":"9401_CR5","doi-asserted-by":"crossref","unstructured":"Bernstein, A.: Fully dynamic approximate all-pairs shortest paths with query and close to linear update time. In: Proc. of the 50th FOCS, Atlanta, GA, pp. 50\u201360 (2009)","DOI":"10.1109\/FOCS.2009.16"},{"issue":"3","key":"9401_CR6","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1137\/S009753970343912X","volume":"36","author":"T.M. Chan","year":"2006","unstructured":"Chan, T.M.: Dynamic subgraph connectivity with geometric applications. SIAM J. Comput. 36(3), 681\u2013694 (2006)","journal-title":"SIAM J. Comput."},{"key":"9401_CR7","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B. Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Int. J. Comput. Geom. Appl. 5, 125\u2013144 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9401_CR8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9401_CR9","unstructured":"Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. In: Proc. of 15th SODA, pp. 362\u2013371 (2004)"},{"issue":"1","key":"9401_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"Even, S., Shiloach, Y.: An on-line edge-deletion problem. J. ACM 28(1), 1\u20134 (1981)","journal-title":"J. ACM"},{"key":"9401_CR11","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9401_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1997.2620","volume":"134","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest distances for graphs with small integer length edges. Inf. Comput. 134, 103\u2013139 (1997)","journal-title":"Inf. Comput."},{"key":"9401_CR13","doi-asserted-by":"crossref","first-page":"1479","DOI":"10.1137\/S0097539700382947","volume":"31","author":"J. Gudmundsson","year":"2002","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithm for constructing sparse geometric spanners. SIAM J. Comput. 31, 1479\u20131500 (2002)","journal-title":"SIAM J. Comput."},{"key":"9401_CR14","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Improved shortest paths on the word RAM. In: Proc. of 27th ICALP, pp. 61\u201372 (2000)","DOI":"10.1007\/3-540-45022-X_7"},{"key":"9401_CR15","doi-asserted-by":"crossref","unstructured":"Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. of 36th FOCS, pp. 664\u2013672 (1995)","DOI":"10.1109\/SFCS.1995.492668"},{"key":"9401_CR16","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1137\/0222071","volume":"22","author":"D.R. Karger","year":"1993","unstructured":"Karger, D.R., Koller, D., Phillips, S.J.: Finding the hidden path: time bounds for all-pairs shortest paths. SIAM J. Comput. 22, 1199\u20131217 (1993)","journal-title":"SIAM J. Comput."},{"key":"9401_CR17","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"1","key":"9401_CR18","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","volume":"312","author":"S. Pettie","year":"2004","unstructured":"Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci. 312(1), 47\u201374 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9401_CR19","doi-asserted-by":"crossref","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S. Pettie","year":"2005","unstructured":"Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398\u20131431 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9401_CR20","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.W.: An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms 21(2), 267\u2013305 (1996)","journal-title":"J. Algorithms"},{"key":"9401_CR21","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proc. of 43rd FOCS, pp. 679\u2013688 (2002)","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"9401_CR22","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. of 45th FOCS, pp. 499\u2013508 (2004)","DOI":"10.1109\/FOCS.2004.22"},{"key":"9401_CR23","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proc. of 36th STOC, pp. 184\u2013191 (2004)","DOI":"10.1145\/1007352.1007387"},{"key":"9401_CR24","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: ICALP, pp. 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"9401_CR25","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9401_CR26","doi-asserted-by":"crossref","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proc. of 40th FOCS, pp. 605\u2013614 (1999)","DOI":"10.1109\/SFFCS.1999.814635"},{"key":"9401_CR27","first-page":"362","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J.\u00a0ACM 46, 362\u2013394 (1999)","journal-title":"J.\u00a0ACM"},{"key":"9401_CR28","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Proc. of 9th SWAT, pp. 384\u2013396 (2004)","DOI":"10.1007\/978-3-540-27810-8_33"},{"issue":"1","key":"9401_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"9401_CR30","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"J.D. Ullman","year":"1991","unstructured":"Ullman, J.D., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM J. Comput. 20, 100\u2013125 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9401_CR31","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Trans. Algorithms 1(1), 2\u201313 (2005)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9401-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9401-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9401-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T22:45:33Z","timestamp":1739918733000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9401-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,3]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9401"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9401-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,3]]}}}