{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:43:48Z","timestamp":1792111428247,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":23,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_151","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:51:54Z","timestamp":1553097114000},"page":"790-792","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fully Dynamic All Pairs Shortest Paths"],"prefix":"10.1007","author":[{"given":"Giuseppe Giuseppe","family":"Italiano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"4","key":"151_CR6278","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1016\/0196-6774(91)90036-X","volume":"12","author":"G Ausiello","year":"1991","unstructured":"Ausiello G, Italiano GF, Marchetti-Spaccamela A, Nanni U (1991) Incremental algorithms for minimal length paths. J Algorithm 12(4):615\u2013638","journal-title":"J Algorithm"},{"key":"151_CR6279","unstructured":"Demetrescu C (2001) Fully dynamic algorithms for path problems on directed graphs. PhD thesis, Department of Computer and Systems Science, University of Rome \u201cLa Sapienza\u201d, Rome"},{"issue":"6","key":"151_CR6280","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demetrescu","year":"2004","unstructured":"Demetrescu C, Italiano GF (2004) A new approach to dynamic all pairs shortest paths. J Assoc Comput Mach 51(6):968\u2013992","journal-title":"J Assoc Comput Mach"},{"key":"151_CR6281","doi-asserted-by":"crossref","unstructured":"Demetrescu C, Italiano GF (2006) Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans Algorithms 2(4):578\u2013601","DOI":"10.1145\/1198513.1198519"},{"issue":"2","key":"151_CR6282","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/1059513.1059514","volume":"52","author":"C Demetrescu","year":"2005","unstructured":"Demetrescu C, Italiano GF (2005) Trade-offs for fully dynamic reachability on dags: breaking through the O(n2) barrier. J Assoc Comput Mach 52(2):147\u2013156","journal-title":"J Assoc Comput Mach"},{"issue":"5","key":"151_CR6283","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1016\/j.jcss.2005.05.005","volume":"72","author":"C Demetrescu","year":"2006","unstructured":"Demetrescu C, Italiano GF (2006) Fully dynamic all pairs shortest paths with real edge weights. J Comput Syst Sci 72(5):813\u2013837","journal-title":"J Comput Syst Sci"},{"key":"151_CR6284","first-page":"371","volume":"49","author":"S Even","year":"1985","unstructured":"Even S, Gazit H (1985) Updating distances in dynamic graphs. Method Oper Res 49:371\u2013387","journal-title":"Method Oper Res"},{"issue":"3","key":"151_CR6285","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/PL00009224","volume":"22","author":"D Frigioni","year":"1998","unstructured":"Frigioni D, Marchetti-Spaccamela A, Nanni U (1998) Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica 22(3):250\u2013274","journal-title":"Algorithmica"},{"key":"151_CR6286","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1006\/jagm.1999.1048","volume":"34","author":"D Frigioni","year":"2000","unstructured":"Frigioni D, Marchetti-Spaccamela A, Nanni U (2000) Fully dynamic algorithms for maintaining shortest paths trees. J Algorithm 34:351\u2013381","journal-title":"J Algorithm"},{"key":"151_CR6287","doi-asserted-by":"crossref","unstructured":"Henzinger M, King V (1995) Fully dynamic biconnectivity and transitive closure. In: Proceedings of the 36th IEEE symposium on foundations of computer science (FOCS'95), Los Alamos. IEEE Computer Society, pp 664\u2013672","DOI":"10.1109\/SFCS.1995.492668"},{"issue":"2","key":"151_CR6288","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0097539797327209","volume":"31","author":"M Henzinger","year":"2001","unstructured":"Henzinger M, King V (2001) Maintaining minimum spanning forests in dynamic graphs. SIAM J Comput 31(2):364\u2013374","journal-title":"SIAM J Comput"},{"issue":"4","key":"151_CR6289","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"MR Henzinger","year":"1999","unstructured":"Henzinger MR, King V (1999) Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J ACM 46(4):502\u2013516","journal-title":"J ACM"},{"key":"151_CR6290","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm J, de Lichtenberg K, Thorup M (2001) Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J ACM 48:723\u2013760","journal-title":"J ACM"},{"key":"151_CR6291","doi-asserted-by":"crossref","unstructured":"King V (1999) Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proceedings of the 40th IEEE symposium on foundations of computer science (FOCS'99), Los Alamos. IEEE Computer Society, pp\u00a081\u201399","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"1","key":"151_CR6292","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1006\/jcss.2002.1883","volume":"65","author":"V King","year":"2002","unstructured":"King V, Sagert G (2002) A fully dynamic algorithm for maintaining the transitive closure. J Comput Syst Sci 65(1):150\u2013167","journal-title":"J Comput Syst Sci"},{"key":"151_CR6293","first-page":"268","volume-title":"Proceedings of the 7th annual international computing and combinatorics conference (COCOON). LNCS","author":"V King","year":"2001","unstructured":"King V, Thorup M (2001) A space saving trick for directed dynamic transitive closure and shortest path algorithms. In: Proceedings of the 7th annual international computing and combinatorics conference (COCOON). LNCS, vol 2108. Springer, Berlin, pp\u00a0268\u2013277"},{"key":"151_CR6294","first-page":"96","volume":"205","author":"P Loubal","year":"1967","unstructured":"Loubal P (1967) A network evaluation procedure. Highw Res Rec 205:96\u2013109","journal-title":"Highw Res Rec"},{"key":"151_CR6295","unstructured":"Murchland J (1967) The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, London"},{"key":"151_CR6296","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam G, Reps T (1996) An incremental algorithm for a generalization of the shortest path problem. J Algorithm 21:267\u2013305","journal-title":"J Algorithm"},{"issue":"5","key":"151_CR6297","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/0041-5553(68)90148-1","volume":"8","author":"V Rodionov","year":"1968","unstructured":"Rodionov V (1968) The parametric problem of shortest distances. USSR Comput Math Math Phys 8(5):336\u2013343","journal-title":"USSR Comput Math Math Phys"},{"key":"151_CR6298","first-page":"279","volume-title":"Proceedings of the 2nd annual symposium on theoretical aspects of computer science, (STACS'85). LNCS","author":"H Rohnert","year":"1985","unstructured":"Rohnert H (1985) A dynamization of the all-pairs least cost problem. In: Proceedings of the 2nd annual symposium on theoretical aspects of computer science, (STACS'85). LNCS, vol 182. Springer, Berlin, pp 279\u2013286"},{"key":"151_CR6299","first-page":"384","volume-title":"Proceedings of the 9th Scandinavian workshop on algorithm theory (SWAT'04), Humlebaek","author":"M Thorup","year":"2004","unstructured":"Thorup M (2004) Fully-dynamic all-pairs shortest paths: faster and allowing negative cycles. In: Proceedings of the 9th Scandinavian workshop on algorithm theory (SWAT'04), Humlebaek. Springer, Berlin, pp 384\u2013396"},{"key":"151_CR6300","volume-title":"Proceedings of the 37th ACM symposium on theory of computing (STOC 2005)","author":"M Thorup","year":"2005","unstructured":"Thorup M (2005) Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proceedings of the 37th ACM symposium on theory of computing (STOC 2005). ACM, New York"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:44:43Z","timestamp":1792107883000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_151","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}