{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:31Z","timestamp":1781077711317,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540241317","type":"print"},{"value":"9783540305514","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":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_78","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"921-932","source":"Crossref","is-referenced-by-count":18,"title":["A Slightly Improved Sub-cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths"],"prefix":"10.1007","author":[{"given":"Uri","family":"Zwick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"78_CR1","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison-Wesley, Reading (1974)"},{"key":"78_CR2","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jcss.1997.1388","volume":"54","author":"N. Alon","year":"1997","unstructured":"Alon, N., Galil, Z., Margalit, O.: On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences\u00a054, 255\u2013262 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"#cr-split#-78_CR3.1","unstructured":"Arlazarov, V.L., Dinic, E.C., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of a directed graph. In: Doklady Akademii Nauk SSSR, vol.\u00a0194, pp. 487-488 (1970)"},{"key":"#cr-split#-78_CR3.2","unstructured":"English translation in Soviet Mathematics Doklady\u00a011, 1209-1210 (1970)"},{"key":"78_CR4","doi-asserted-by":"publisher","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. Journal of Symbolic Computation\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"78_CR5","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: Breaking through the O(n 2) barrier. In: Proc. of 41st FOCS, pp. 381\u2013389 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"key":"78_CR6","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. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"78_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1080\/00207169008803814","volume":"32","author":"W. Dobosiewicz","year":"1990","unstructured":"Dobosiewicz, W.: A more efficient algorithm for the min-plus multiplication. International Journal of Computer Mathematics\u00a032, 49\u201360 (1990)","journal-title":"International Journal of Computer Mathematics"},{"issue":"6","key":"78_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R.W. Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: Shortest path. Communications of the ACM\u00a05(6), 345 (1962)","journal-title":"Communications of the ACM"},{"key":"78_CR9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM Journal on Computing\u00a05, 49\u201360 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"78_CR10","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. Journal of the ACM\u00a034, 596\u2013615 (1987)","journal-title":"Journal of the ACM"},{"key":"78_CR11","first-page":"524","volume":"194","author":"M.E. Furman","year":"1970","unstructured":"Furman, M.E.: Application of a method of rapid multiplication of matrices to the problem of finding the transitive closure of a graph. Doklady Akademii Nauk SSSR\u00a0194, 524 (1970); English translation in Soviet Mathematics Doklady 11, 1252 (1970)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"78_CR12","doi-asserted-by":"publisher","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. Information and Computation\u00a0134, 103\u2013139 (1997)","journal-title":"Information and Computation"},{"key":"78_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1006\/jcss.1997.1385","volume":"54","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest paths for graphs with small integer length edges. Journal of Computer and System Sciences\u00a054, 243\u2013254 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"78_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":"78_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D.B. Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse graphs. Journal of the ACM\u00a024, 1\u201313 (1977)","journal-title":"Journal of the ACM"},{"key":"78_CR16","doi-asserted-by":"crossref","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. of 40th FOCS, pp. 81\u201391 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"2","key":"78_CR17","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"I. Munro","year":"1971","unstructured":"Munro, I.: Efficient determination of the transitive closure of a directed graph. Information Processing Letters\u00a01(2), 56\u201358 (1971)","journal-title":"Information Processing Letters"},{"issue":"1","key":"78_CR18","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0312(1), 47\u201374 (2004)","journal-title":"Theoretical Computer Science"},{"key":"78_CR19","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. of 13th SODA, pp. 267\u2013276 (2002)"},{"key":"78_CR20","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":"78_CR21","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a051, 400\u2013403 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"78_CR22","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":"78_CR23","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik\u00a013, 354\u2013356 (1969)","journal-title":"Numerische Mathematik"},{"key":"78_CR24","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.: A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters\u00a043, 195\u2013199 (1992)","journal-title":"Information Processing Letters"},{"key":"78_CR25","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM\u00a046, 362\u2013394 (1999)","journal-title":"Journal of the ACM"},{"issue":"1","key":"78_CR26","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S. Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on boolean matrices. Journal of the ACM\u00a09(1), 11\u201312 (1962)","journal-title":"Journal of the ACM"},{"key":"78_CR27","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0020-0190(76)90085-5","volume":"4","author":"G. Yuval","year":"1976","unstructured":"Yuval, G.: An algorithm for finding all shortest paths using N 2.81 infinite-precision multiplications. Information Processing Letters\u00a04, 155\u2013156 (1976)","journal-title":"Information Processing Letters"},{"key":"78_CR28","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Exact and approximate distances in graphs \u2013 a survey. In: Proc. of 9th ESA, pp. 33\u201348 (2001)","DOI":"10.1007\/3-540-44676-1_3"},{"key":"78_CR29","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All-pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM\u00a049, 289\u2013317 (2002)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_78","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:52:38Z","timestamp":1740261158000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_78","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}