{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:37:21Z","timestamp":1725521841589},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540001423"},{"type":"electronic","value":"9783540361367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36136-7_4","type":"book-chapter","created":{"date-parts":[[2008,11,25]],"date-time":"2008-11-25T19:07:11Z","timestamp":1227640031000},"page":"32-43","source":"Crossref","is-referenced-by-count":14,"title":["On the Comparison-Addition Complexity of All-Pairs Shortest Paths"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,8]]},"reference":[{"key":"4_CR1","unstructured":"T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, 2001."},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connexion with graphs. In Numer. Math., 1 (1959), 269\u2013271.","journal-title":"Numer. Math."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M. Fredman","year":"1976","unstructured":"M. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5 (1976), no. 1, 83\u201389.","journal-title":"SIAM J. Comput."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman, R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. In JACM 34 (1987), 596\u2013615.","journal-title":"JACM"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"H. N. Gabow. A scaling algorithm for weighted matching on general graphs. In 26th Ann. Symp. on Foundations of Computer Science (FOCS 1985), 90\u201399.","DOI":"10.1109\/SFCS.1985.3"},{"key":"4_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-45022-X_7","volume-title":"Proceedings 27th Int\u2019l Colloq. on Automata, Languages and Programming (ICALP 2000)","author":"T. Hagerup","year":"2000","unstructured":"T. Hagerup. Improved shortest paths on the word RAM. In Proceedings 27th Int\u2019l Colloq. on Automata, Languages and Programming (ICALP 2000), LNCS volume 1853, 61\u201372."},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D. B. Johnson","year":"1977","unstructured":"D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. JACM 24 (1977), 1\u201313.","journal-title":"JACM"},{"issue":"6","key":"4_CR8","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1137\/0222071","volume":"22","author":"D. R. Karger","year":"1993","unstructured":"D. R. Karger, D. Koller, S. J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths. SIAM J. on Comput. 22 (1993), no. 6, 1199\u20131217.","journal-title":"SIAM J. on Comput."},{"key":"4_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-45465-9_9","volume-title":"Proceedings 29th Int\u2019l Colloq. on Automata, Languages and Programming (ICALP 2002)","author":"S. Pettie","year":"2002","unstructured":"S. Pettie. A faster all-pairs shortest path algorithm for real-weighted sparse graphs. Proceedings 29th Int\u2019l Colloq. on Automata, Languages and Programming (ICALP 2002), LNCS 2380, 85\u201397."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"S. Pettie. On the comparison-addition complexity of all-pairs shortest paths. UTCS Technical Report TR-02-21, May 2002.","DOI":"10.1007\/3-540-36136-7_4"},{"key":"4_CR11","unstructured":"S. Pettie, V. Ramachandran. Computing shortest paths with comparisons and additions (extended abstract). Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, 267\u2013276."},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"S. Pettie, V. Ramachandran, S. Sridhar. Experimental evaluation of a new shortest path algorithm. 4th Workshop on Algorithm, Engineering and Experiments (ALENEX), 2002.","DOI":"10.1007\/3-540-45643-0_10"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"G. Ramalingam, T. Reps. An incremental algorithm for a generalization of the shortest path problem. J. Algorithms 21 (1996), 267\u2013305.","journal-title":"J. Algorithms"},{"issue":"4","key":"4_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T. Takaoka","year":"1992","unstructured":"T. Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Inform. Process. Lett. 43 (1992), no. 4, 195\u2013199.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"M. Thorup. Undirected single source shortest paths with positive integer weights in linear time. JACM 46 (1999), no. 3, 362\u2013394.","journal-title":"JACM"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"U. Zwick. Exact and approximate distances in graphs \u2014 A survey. Updated version at http:\/\/www.cs.tau.ac.il\/zwick\/ Proc. of 9th ESA (2001), 33\u201348.","DOI":"10.1007\/3-540-44676-1_3"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36136-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T18:29:06Z","timestamp":1557944946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36136-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540001423","9783540361367"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-36136-7_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}