{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T18:46:06Z","timestamp":1776451566551,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540223399","type":"print"},{"value":"9783540278108","type":"electronic"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_33","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"384-396","source":"Crossref","is-referenced-by-count":42,"title":["Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles"],"prefix":"10.1007","author":[{"given":"Mikkel","family":"Thorup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths. In: Proc. 35th STOC, pp. 159\u2013166 (2003)","DOI":"10.1145\/780542.780567"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths (2004) ,Full version of [1] available at http:\/\/www.dis.uniroma1.it\/~demetres\/","DOI":"10.1145\/780542.780567"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math.\u00a01, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"3","key":"33_CR4","doi-asserted-by":"publisher","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\u00a034(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"2","key":"33_CR5","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0097539797327209","volume":"31","author":"M.R. Henzinger","year":"2001","unstructured":"Henzinger, M.R., King, V.: Maintaining minimum spanning forests in dynamic graphs. SIAM J. Computing\u00a031(2), 364\u2013374 (2001)","journal-title":"SIAM J. Computing"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th FOCS, pp. 81\u201389 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"33_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/3-540-44679-6_30","volume-title":"Computing and Combinatorics","author":"V. King","year":"2001","unstructured":"King, V., Thorup, M.: A space saving trick for directed dynamic transitive closure and shortest path algorithms. In: Wang, J. (ed.) COCOON 2001. LNCS, vol.\u00a02108, pp. 268\u2013277. Springer, Heidelberg (2001)"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-45465-9_9","volume-title":"Automata, Languages and Programming","author":"S. Pettie","year":"2002","unstructured":"Pettie, S.: A faster all-pairs shortest path algorithm for real-weighted sparse graphs. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 85\u201397. Springer, Heidelberg (2002)"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. In: Proc. 35th STOC, pp. 149\u2013158 (2003)","DOI":"10.1145\/780542.780566"},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths (2004) (submitted)","DOI":"10.1145\/1060590.1060607"},{"issue":"6","key":"33_CR11","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232. Comm. ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Comm. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:51:41Z","timestamp":1740261101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}