{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:30:15Z","timestamp":1772908215912,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540281016","type":"print"},{"value":"9783540317111","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11534273_28","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T08:31:47Z","timestamp":1268382707000},"page":"318-324","source":"Crossref","is-referenced-by-count":22,"title":["All-Pairs Shortest Paths with Real Weights in O(n 3\/log n) Time"],"prefix":"10.1007","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_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":"28_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. J. Comput. Sys. Sci.\u00a054, 255\u2013262 (1997)","journal-title":"J. Comput. Sys. Sci."},{"key":"28_CR3","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.C., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of a directed graph. Soviet Math. Dokl.\u00a011, 1209\u20131210 (1970)","journal-title":"Soviet Math. Dokl."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators. In: Proc. 30th ACM Sympos. Theory Comput., pp. 279\u2013288 (1998)","DOI":"10.1145\/276698.276764"},{"key":"28_CR5","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. J. Symbolic Comput.\u00a09, 251\u2013280 (1990)","journal-title":"J. Symbolic Comput."},{"key":"28_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, New York (2001)","edition":"2"},{"key":"28_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. Int. J. Computer Math.\u00a032, 49\u201360 (1990)","journal-title":"Int. J. Computer Math."},{"key":"28_CR8","unstructured":"Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pp. 788\u2013797 (2004)"},{"key":"28_CR9","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1006\/jcss.1995.1065","volume":"51","author":"T. Feder","year":"1995","unstructured":"Feder, T., Motwani, R.: Clique partitions, graph compression and speeding-up algorithms. J. Comput. Sys. Sci.\u00a051, 261\u2013272 (1995)","journal-title":"J. Comput. Sys. Sci."},{"key":"28_CR10","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 J. Comput.\u00a05, 49\u201360 (1976)","journal-title":"SIAM J. Comput."},{"key":"28_CR11","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. J. Comput. Sys. Sci.\u00a054, 243\u2013254 (1997)","journal-title":"J. Comput. Sys. Sci."},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.ipl.2004.05.006","volume":"91","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Improved algorithm for all pairs shortest paths. Inform. Process. Lett.\u00a091, 245\u2013250 (2004)","journal-title":"Inform. Process. Lett."},{"key":"28_CR13","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. Theoret. Comput. Sci.\u00a0312, 47\u201374 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. (to appear)","DOI":"10.1137\/S0097539702419650"},{"key":"28_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"28_CR16","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. J. Comput. Sys. Sci.\u00a051, 400\u2013403 (1995)","journal-title":"J. Comput. Sys. Sci."},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proc. 40th IEEE Sympos. Found. Comput. Sci., pp. 605\u2013614 (1999)","DOI":"10.1109\/SFFCS.1999.814635"},{"key":"28_CR18","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":"28_CR19","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. Inform. Process. Lett.\u00a043, 195\u2013199 (1992)","journal-title":"Inform. Process. Lett."},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-540-27798-9_31","volume-title":"Computing and Combinatorics","author":"T. Takaoka","year":"2004","unstructured":"Takaoka, T.: A faster algorithm for the all-pairs shortest path problem and its application. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol.\u00a03106, pp. 278\u2013289. Springer, Heidelberg (2004)"},{"key":"28_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1007\/978-3-540-30140-0_54","volume-title":"Algorithms \u2013 ESA 2004","author":"R. Yuster","year":"2004","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 604\u2013615. Springer, Heidelberg (2004)"},{"key":"28_CR22","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. J. ACM\u00a049, 289\u2013317 (2002)","journal-title":"J. ACM"},{"key":"28_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1007\/978-3-540-30551-4_78","volume-title":"Algorithms and Computation","author":"U. Zwick","year":"2004","unstructured":"Zwick, U.: A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 921\u2013932. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11534273_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:09:58Z","timestamp":1605625798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11534273_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281016","9783540317111"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11534273_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}