{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:34:08Z","timestamp":1794357248635,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":23,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_151","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:35:59Z","timestamp":1214490959000},"page":"329-331","source":"Crossref","is-referenced-by-count":0,"title":["Fully Dynamic All Pairs Shortest Paths"],"prefix":"10.1007","author":[{"given":"Giuseppe F.","family":"Italiano","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"151_CR1_151","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, G.F., Marchetti-Spaccamela, A., Nanni, U.: Incremental algorithms for minimal length paths. J.\u00a0Algorithm 12(4), 615\u201338 (1991)","journal-title":"J. Algorithm"},{"key":"151_CR2_151","unstructured":"Demetrescu, C.: Fully Dynamic Algorithms for Path Problems on Directed Graphs. Ph.\u202fD. thesis, Department of Computer and Systems Science, University of Rome \u201cLa Sapienza\u201d, Rome (2001)"},{"issue":"6","key":"151_CR3_151","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C. Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.F.: A\u00a0new approach to dynamic all pairs shortest paths. J.\u00a0Assoc. Comp. Mach. 51(6), 968\u2013992 (2004)","journal-title":"J. Assoc. Comp. Mach."},{"issue":"4","key":"151_CR4_151","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/1198513.1198519","volume":"2","author":"C. Demetrescu","year":"2006","unstructured":"Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. Algorithms 2(4), 578\u2013601 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"151_CR5_151","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1145\/1059513.1059514","volume":"52","author":"C. Demetrescu","year":"2005","unstructured":"Demetrescu, C., Italiano, G.F.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n 2) barrier. J.\u00a0Assoc. Comp. Mach. 52(2), 147\u2013156 (2005)","journal-title":"J. Assoc. Comp. Mach."},{"issue":"5","key":"151_CR6_151","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, G.F.: Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. J.\u00a0Comp. Syst. Sci. 72(5), 813\u2013837 (2006)","journal-title":"J. Comp. Syst. Sci."},{"key":"151_CR7_151","first-page":"371","volume":"49","author":"S. Even","year":"1985","unstructured":"Even, S., Gazit, H.: Updating distances in dynamic graphs. Method. Oper. Res. 49, 371\u2013387 (1985)","journal-title":"Method. Oper. Res."},{"issue":"3","key":"151_CR8_151","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.: Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica 22(3), 250\u2013274 (1998)","journal-title":"Algorithmica"},{"key":"151_CR9_151","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.: Fully dynamic algorithms for maintaining shortest paths trees. J.\u00a0Algorithm 34, 351\u2013381 (2000)","journal-title":"J. Algorithm"},{"key":"151_CR10_151","doi-asserted-by":"crossref","unstructured":"Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95). IEEE Computer Society, pp.\u00a0664\u2013672. Los Alamos (1995)","DOI":"10.1109\/SFCS.1995.492668"},{"issue":"2","key":"151_CR11_151","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0097539797327209","volume":"31","author":"M. Henzinger","year":"2001","unstructured":"Henzinger, M., King, V.: Maintaining minimum spanning forests in dynamic graphs. SIAM J.\u00a0Comp. 31(2), 364\u2013374 (2001)","journal-title":"SIAM J. Comp."},{"issue":"4","key":"151_CR12_151","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"M.R. Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J.\u00a0ACM 46(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"key":"151_CR13_151","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de\u00a0Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J.\u00a0ACM 48, 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"151_CR14_151","first-page":"81","volume-title":"Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS'99)","author":"V. King","year":"1999","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS'99). IEEE Computer Society pp.\u00a081\u201399. Los Alamos (1999)"},{"issue":"1","key":"151_CR15_151","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.: A\u00a0fully dynamic algorithm for maintaining the transitive closure. J.\u00a0Comp. Syst. Sci. 65(1), 150\u2013167 (2002)","journal-title":"J. Comp. Syst. Sci."},{"key":"151_CR16_151","first-page":"268","volume-title":"Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON). LNCS, vol. 2108","author":"V. King","year":"2001","unstructured":"King, V., Thorup, M.: A\u00a0space 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.\u00a02108, pp.\u00a0268\u2013277. Springer, Berlin (2001)"},{"key":"151_CR17_151","first-page":"96","volume":"205","author":"P. Loubal","year":"1967","unstructured":"Loubal, P.: A\u00a0network evaluation procedure. Highway Res. Rec. 205, 96\u2013109 (1967)","journal-title":"Highway Res. Rec."},{"key":"151_CR18_151","unstructured":"Murchland, J.: The effect of increasing or decreasing the length of a\u00a0single arc on all shortest distances in a\u00a0graph. Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, London (1967)"},{"key":"151_CR19_151","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.: An incremental algorithm for a\u00a0generalization of the shortest path problem. J.\u00a0Algorithm 21, 267\u2013305 (1996)","journal-title":"J. Algorithm"},{"issue":"5","key":"151_CR20_151","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.: The parametric problem of shortest distances. USSR Comp. Math. Math. Phys. 8(5), 336\u2013343 (1968)","journal-title":"USSR Comp. Math. Math. Phys."},{"key":"151_CR21_151","first-page":"279","volume-title":"Proc. 2nd Annual Symposium on Theoretical Aspects of Computer Science, (STACS'85). LNCS, vol. 182","author":"H. Rohnert","year":"1985","unstructured":"Rohnert, H.: A\u00a0dynamization of the all-pairs least cost problem. In: Proc. 2nd Annual Symposium on Theoretical Aspects of Computer Science, (STACS'85). LNCS, vol.\u00a0182, pp.\u00a0279\u2013286. Springer, Berlin (1985)"},{"key":"151_CR22_151","first-page":"384","volume-title":"Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04)","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT'04), pp.\u00a0384\u2013396. Springer, Berlin (2004)"},{"key":"151_CR23_151","doi-asserted-by":"crossref","unstructured":"Thorup, M.: 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 (2005)","DOI":"10.1145\/1060590.1060607"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T16:32:32Z","timestamp":1738254752000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_151"}},"subtitle":["2004; Demetrescu, Italiano"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_151","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}