{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:28Z","timestamp":1781077708997,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,3]],"date-time":"2007-10-03T00:00:00Z","timestamp":1191369600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s00453-007-9063-0","type":"journal-article","created":{"date-parts":[[2007,10,2]],"date-time":"2007-10-02T11:55:26Z","timestamp":1191326126000},"page":"428-434","source":"Crossref","is-referenced-by-count":19,"title":["An O(n 3(log\u2009log\u2009n\/log\u2009n)5\/4) Time Algorithm for All Pairs Shortest Path"],"prefix":"10.1007","volume":"51","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,10,3]]},"reference":[{"key":"9063_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":"9063_CR2","volume-title":"Data Structures and Algorithms","author":"A.V. Aho","year":"1983","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley, Reading (1983)"},{"key":"9063_CR3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1006\/inco.1997.2632","volume":"136","author":"S. Albers","year":"1997","unstructured":"Albers, S., Hagerup, T.: Improved parallel integer sorting without concurrent writing. Inf. Comput. 136, 25\u201351 (1997)","journal-title":"Inf. Comput."},{"key":"9063_CR4","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: Proc. 1968 AFIPS Spring Joint Summer Computer Conference, pp.\u00a0307\u2013314 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"9063_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/11576259","volume-title":"Proc. 9th Workshop Algorithms Data Structures","author":"T.M. Chan","year":"2005","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in O(n 3\/log\u2009n) time. In: Proc. 9th Workshop Algorithms Data Structures. Lecture Notes in Computer Science, vol. 3608, pp.\u00a0318\u2013324. Springer, New York (2005)"},{"key":"9063_CR6","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1080\/00207169008803814","volume":"32","author":"W. Dobosiewicz","year":"1990","unstructured":"Dobosiewicz, W.: A more efficient algorithm for min-plus multiplication. Int. J. Comput. Math. 32, 49\u201360 (1990)","journal-title":"Int. J. Comput. Math."},{"key":"9063_CR7","doi-asserted-by":"crossref","first-page":"83","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. 5, 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"key":"9063_CR8","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9063_CR9","doi-asserted-by":"crossref","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. Inf. Comput. 134, 103\u2013139 (1997)","journal-title":"Inf. Comput."},{"key":"9063_CR10","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.ipl.2004.05.006","volume":"91","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Improved algorithms for all pairs shortest paths. Inf. Process. Lett. 91, 245\u2013250 (2004)","journal-title":"Inf. Process. Lett."},{"key":"9063_CR11","unstructured":"Han, Y.: Achieving O(n 3\/log\u2009n) time for all pairs shortest paths by using a smaller table. In: Proc. 21st Int. Conf. on Computers and Their Applications (CATA-2006), Seattle, Washington, pp.\u00a036\u201337 (2006). To appear in Information Processing Letters as \u201cA note of an O(n 3\/log\u2009n) time algorithm for all pairs shortest paths\u201d"},{"key":"9063_CR12","doi-asserted-by":"crossref","unstructured":"Pettie, S.: A faster all-pairs shortest path algorithm for real-weighted sparse graphs. In: Proceedings of 29th International Colloquium on Automata, Languages, and Programming (ICALP\u201902). Lecture Notes in Computer Science, vol. 2380, pp.\u00a085-97 (2002)","DOI":"10.1007\/3-540-45465-9_9"},{"issue":"6","key":"9063_CR13","doi-asserted-by":"crossref","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S. Pettie","year":"2005","unstructured":"Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398\u20131431 (2005)","journal-title":"SIAM J. Comput."},{"key":"9063_CR14","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Shortest paths in matrix multiplication time. In: Proceedings of 13th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol.\u00a03669, pp.\u00a0770\u2013778 (2005)","DOI":"10.1007\/11561071_68"},{"key":"9063_CR15","doi-asserted-by":"crossref","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. Syst. Sci. 51, 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9063_CR16","doi-asserted-by":"crossref","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. Inf. Process. Lett. 43, 195\u2013199 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9063_CR17","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.ipl.2005.08.008","volume":"96","author":"T. Takaoka","year":"2005","unstructured":"Takaoka, T.: An O(n 3log\u2009log\u2009n\/log\u2009n) time algorithm for the all-pairs shortest path problem. Inf. Process. Lett. 96, 155\u2013161 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9063_CR18","doi-asserted-by":"crossref","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. J. ACM 46(3), 362\u2013394 (1999)","journal-title":"J. ACM"},{"key":"9063_CR19","doi-asserted-by":"crossref","unstructured":"Yuster, R., Zwick, U.: Answering distance queries in directed graphs using fast matrix multiplication. In: 46th Annual IEEE Symposium on Foundations of Computer Science. Los Alamitos, CA, USA, pp.\u00a0389\u2013396. IEEE Comput. Soc. (2005)","DOI":"10.1109\/SFCS.2005.20"},{"issue":"3","key":"9063_CR20","doi-asserted-by":"crossref","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 49(3), 289\u2013317 (2002)","journal-title":"J. ACM"},{"key":"9063_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1007\/978-3-540-30551-4_78","volume-title":"Proceedings of ISAAC 2004","author":"U. Zwick","year":"2004","unstructured":"Zwick, U.: A slightly improved sub-cubic algorithm for the all pairs shortest paths problem. In: Proceedings of ISAAC 2004. Lecture Notes in Computer Science, vol. 3341, pp.\u00a0921\u2013932. Springer, Berlin (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9063-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9063-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9063-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:00Z","timestamp":1559123100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9063-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,3]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9063"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9063-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,3]]}}}