{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T05:51:56Z","timestamp":1725688316376},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642311543"},{"type":"electronic","value":"9783642311550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31155-0_12","type":"book-chapter","created":{"date-parts":[[2012,6,13]],"date-time":"2012-06-13T02:21:27Z","timestamp":1339554087000},"page":"131-141","source":"Crossref","is-referenced-by-count":11,"title":["An O(n 3 loglogn\/log2 n) Time Algorithm for All Pairs Shortest Paths"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tadao","family":"Takaoka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_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":"12_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":"12_CR3","doi-asserted-by":"publisher","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. Information and Computation\u00a0136, 25\u201351 (1997)","journal-title":"Information and Computation"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: Proc. 1968 AFIPS Spring Joint Summer Computer Conference, pp. 307\u2013314 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proc. 2007 ACM Symp. Theory of Computing, pp. 590\u2013598 (2007)","DOI":"10.1145\/1250790.1250877"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/11534273_28","volume-title":"Algorithms and Data Structures","author":"T.M. Chan","year":"2005","unstructured":"Chan, T.M.: All-Pairs Shortest Paths with Real Weights in O(n\n                3\/logn) Time. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 318\u2013324. Springer, Heidelberg (2005)"},{"key":"12_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 min-plus multiplication. Inter. J. Comput. Math.\u00a032, 49\u201360 (1990)","journal-title":"Inter. J. Comput. Math."},{"key":"12_CR8","doi-asserted-by":"publisher","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. Computing\u00a05, 83\u201389 (1976)","journal-title":"SIAM J. Computing"},{"key":"12_CR9","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.: 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":"12_CR10","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"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-007-9063-0","volume":"51","author":"Y. Han","year":"2008","unstructured":"Han, Y.: An O(n\n                3(loglogn\/logn)5\/4) time algorithm for all pairs shortest paths. Algorithmica\u00a051(4), 428\u2013434 (2008)","journal-title":"Algorithmica"},{"key":"12_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 algorithms for all pairs shortest paths. Information Processing Letters\u00a091, 245\u2013250 (2004)","journal-title":"Information Processing Letters"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.ipl.2007.08.015","volume":"105","author":"Y. Han","year":"2008","unstructured":"Han, Y.: A note of an O(n\n                3\/logn) time algorithm for all pairs shortest paths. Information Processing Letters\u00a0105, 114\u2013116 (2008)","journal-title":"Information Processing Letters"},{"key":"12_CR14","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)"},{"issue":"6","key":"12_CR15","doi-asserted-by":"publisher","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.\u00a034(6), 1398\u20131431 (2005)","journal-title":"SIAM J. Comput."},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1007\/11561071_68","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Sankowski","year":"2005","unstructured":"Sankowski, P.: Shortest Paths in Matrix Multiplication Time. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 770\u2013778. Springer, Heidelberg (2005)"},{"key":"12_CR17","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. Syst. Sci.\u00a051, 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"14","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik\u00a014(3), 354\u2013356 (1969)","journal-title":"Numerische Mathematik"},{"key":"12_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. Information Processing Letters\u00a043, 195\u2013199 (1992)","journal-title":"Information Processing Letters"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.ipl.2005.08.008","volume":"96","author":"T. Takaoka","year":"2005","unstructured":"Takaoka, T.: An O(n\n                3 loglogn\/logn) time algorithm for the all-pairs shortest path problem. Information Processing Letters\u00a096, 155\u2013161 (2005)","journal-title":"Information Processing Letters"},{"issue":"3","key":"12_CR21","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 ACM\u00a046(3), 362\u2013394 (1999)","journal-title":"Journal of ACM"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1109\/SFCS.2005.20","volume-title":"46th Annual IEEE Symposium on Foundations of Computer Science","author":"R. Yuster","year":"2005","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, pp. 389\u2013396. IEEE Comput. Soc., Los Alamitos (2005)"},{"issue":"3","key":"12_CR23","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(3), 289\u2013317 (2002)","journal-title":"Journal of the ACM"},{"key":"12_CR24","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","Algorithm Theory \u2013 SWAT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31155-0_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:48:26Z","timestamp":1620128906000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31155-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642311543","9783642311550"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31155-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}