{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:20:25Z","timestamp":1725571225000},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642174605"},{"type":"electronic","value":"9783642174612"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17461-2_16","type":"book-chapter","created":{"date-parts":[[2010,12,15]],"date-time":"2010-12-15T04:53:59Z","timestamp":1292388839000},"page":"195-206","source":"Crossref","is-referenced-by-count":3,"title":["A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n 2logn) Expected Time"],"prefix":"10.1007","author":[{"given":"Tadao","family":"Takaoka","sequence":"first","affiliation":[]},{"given":"Mashitoh","family":"Hashim","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-70575-8_10","volume-title":"Automata, Languages and Programming","author":"G.E. Blelloch","year":"2008","unstructured":"Blelloch, G.E., Vassilevska, V., Williams, R.: A New Combinatorial Approach for Sparse Graph Problems. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 108\u2013120. Springer, Heidelberg (2008)"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1137\/0212039","volume":"12","author":"P. Bloniarz","year":"1983","unstructured":"Bloniarz, P.: A shortest path algorithm with expected time O(n 2lognlog* n). SIAM Journal on Computing\u00a012, 588\u2013600 (1983)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Chan, T.: More algorithms for all pairs shortest paths. In: STOC 2007, pp. 590\u2013598 (2007)","DOI":"10.1145\/1250790.1250877"},{"key":"16_CR4","first-page":"269","volume":"6","author":"G. Dantzig","year":"1960","unstructured":"Dantzig, G.: On the shortest route in a network. Management Science\u00a06, 269\u2013271 (1960)","journal-title":"Management Science"},{"key":"16_CR5","volume-title":"An Introduction to Probability and its Applications","author":"W.H. Feller","year":"1968","unstructured":"Feller, W.H.: An Introduction to Probability and its Applications, 3rd edn., vol.\u00a01. John-Wiley, New York (1968)","edition":"3"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization problems. JACM\u00a034, 596\u2013615 (1987)","journal-title":"JACM"},{"key":"16_CR7","unstructured":"Goldberg, A.V., Tarjan, R.E.: Expected Performance of Dijkstra\u2019s Shortest Path Algorithm, Technical Report 96-062, NEC Research Institute, Inc. (June 1996)"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<205::AID-RSA11>3.0.CO;2-7","volume":"10","author":"K. Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Priebe, V.: On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka. Random Structures and Algorithms\u00a010, 205\u2013220 (1997)","journal-title":"Random Structures and Algorithms"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1137\/0216065","volume":"16","author":"A. Moffat","year":"1987","unstructured":"Moffat, A., Takaoka, T.: An all pairs shortest path algorithm with expected running time O(n 2logn). SIAM Journal on Computing\u00a016, 1023\u20131031 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR10","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, 47\u201374 (2004)","journal-title":"Theoretical Computer Science"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0202004","volume":"2","author":"P. Spira","year":"1973","unstructured":"Spira, P.: A new algorithm for finding all shortest paths in a graph of positive arcs in average time O(n 2log2 n). SIAM Journal on Computing\u00a02, 28\u201332 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/BFb0022539","volume-title":"Mathematical Foundations of Computer Science 1980","author":"T. Takaoka","year":"1980","unstructured":"Takaoka, T., Moffat, A.: An O(n 2lognloglogn) expected time algorithm for the all pairs shortest path problem. In: Dembinski, P. (ed.) MFCS 1980. LNCS, vol.\u00a088, pp. 643\u2013655. Springer, Heidelberg (1980)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17461-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T22:55:12Z","timestamp":1559861712000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17461-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642174605","9783642174612"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17461-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}