{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:43:59Z","timestamp":1792111439799,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":19,"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_102","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:12Z","timestamp":1461268992000},"page":"506-509","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decremental All-Pairs Shortest Paths"],"prefix":"10.1007","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"102_CR474","volume-title":"Network flows: theory, algorithms and applications","author":"R Ahuja","year":"1993","unstructured":"Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms and applications. Prentice Hall, Englewood Cliffs"},{"key":"102_CR475","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demetrescu","year":"2004","unstructured":"Demetrescu C, Italiano G (2004) A new approach to dynamic all pairs shortest paths. J Assoc Comput Mach 51:968\u2013992","journal-title":"J Assoc Comput Mach"},{"key":"102_CR476","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E Dijkstra","year":"1959","unstructured":"Dijkstra E (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"102_CR477","first-page":"371","volume":"49","author":"S Even","year":"1985","unstructured":"Even S, Gazit H (1985) Updating distances in dynamic graphs. Methods Oper Res 49:371\u2013387","journal-title":"Methods Oper Res"},{"key":"102_CR478","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M Fredman","year":"1987","unstructured":"Fredman M, Tarjan R (1987) Fibonacci heaps and their use in improved network optimization algorithms. J ACM 34:596\u2013615","journal-title":"J ACM"},{"issue":"1","key":"102_CR479","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/0205006","volume":"5","author":"ML Fredman","year":"1976","unstructured":"Fredman ML (1976) New bounds on the complexity of the shortest path problems. SIAM J Comput 5(1):87\u201389","journal-title":"SIAM J Comput"},{"key":"102_CR480","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:250\u2013274","journal-title":"Algorithmica"},{"key":"102_CR481","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":"102_CR482","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 40th IEEE symposium on foundations of computer science (FOCS\u201999). IEEE Computer Society, New York, pp 81\u201399","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"102_CR483","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1002\/spe.4380111102","volume":"11","author":"D Knuth","year":"1981","unstructured":"Knuth D, Plass M (1981) Breaking paragraphs into lines. Softw-Pract Exp 11:1119\u20131184","journal-title":"Softw-Pract Exp"},{"key":"102_CR484","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":"102_CR485","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":"102_CR486","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","volume":"312","author":"S Pettie","year":"2003","unstructured":"Pettie S (2003) A new approach to all-pairs shortest paths on realweighted graphs. Theor Comput Sci 312:47\u201374, Special issue of selected papers from ICALP (2002)","journal-title":"Theor Comput Sci"},{"key":"102_CR487","doi-asserted-by":"crossref","unstructured":"Ramalingam G (1996) Bounded incremental computation. Lect Note Comput Sci 1089","DOI":"10.1007\/BFb0028290"},{"key":"102_CR488","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"},{"key":"102_CR489","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-3975(95)00079-8","volume":"158","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam G, Reps T (1996) On the computational complexity of dynamic graph problems. Theor Comput Sci 158:233\u2013277","journal-title":"Theor Comput Sci"},{"key":"102_CR490","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:336\u2013343","journal-title":"USSR Comput Math Math Phys"},{"key":"102_CR491","doi-asserted-by":"crossref","unstructured":"Schulz F, Wagner D, Weihe K (1999) Dijkstra\u2019s algorithm on-line: an empirical case study frompublic railroad transport. In: Proceedings of 3rd workshop on algorithm engineering (WAE\u201999), London. Notes in computer science, vol 1668, pp 110\u2013123","DOI":"10.1007\/3-540-48318-7_11"},{"key":"102_CR492","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T Takaoka","year":"1992","unstructured":"Takaoka T (1992) A new upper bound on the complexity of the all pairs shortest path problem. Inf Proc Lett 43:195--199","journal-title":"Inf Proc Lett"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:46:28Z","timestamp":1792107988000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_102","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"}}]}}