{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:10:34Z","timestamp":1725484234994},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_9","type":"book-chapter","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T21:12:57Z","timestamp":1180213977000},"page":"85-97","source":"Crossref","is-referenced-by-count":12,"title":["A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"9_CR1","unstructured":"T. Cormen, C. Leiserson, R. Rivest. Intro. to Algorithms. MIT Press, 1990."},{"key":"9_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":"9_CR3","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":"9_CR4","doi-asserted-by":"crossref","unstructured":"H. N. Gabow. A scaling algorithm for weighted matching on general graphs. In Proc. FOCS 1985, 90\u201399.","DOI":"10.1109\/SFCS.1985.3"},{"key":"9_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/3-540-45022-X_7","volume-title":"Proc. ICALP 2000","author":"T. Hagerup","year":"2000","unstructured":"T. Hagerup. Improved shortest paths on the word RAM. In Proc. ICALP 2000, LNCS volume 1853, 61\u201372."},{"key":"9_CR6","doi-asserted-by":"crossref","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. J. Assoc. Comput. Mach. 24 (1977), 1\u201313.","journal-title":"J. Assoc. Comput. Mach."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"S. Pettie. A faster all-pairs shortest path algorithm for real-weighted sparse graphs. UTCS Technical Report CS-TR-02-13, February, 2002.","DOI":"10.1007\/3-540-45465-9_9"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"S. Pettie. On the comparison-addition complexity of all-pairs shortest paths. UTCS Technical Report CS-TR-02-21, April, 2002.","DOI":"10.1007\/3-540-36136-7_4"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"S. Pettie, V. Ramachandran, S. Sridhar. Experimental evaluation of a new shortest path algorithm. Proceedings of ALENEX 2002.","DOI":"10.1007\/3-540-45643-0_10"},{"key":"9_CR10","unstructured":"S. Pettie, V. Ramachandran. Computing shortest paths with comparisons and additions. Proceedings of SODA 2002, 267\u2013276."},{"issue":"2","key":"9_CR11","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18 (1979), no. 2, 110\u2013127.","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9_CR12","doi-asserted-by":"crossref","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. J. Assoc. Comput. Mach. 46 (1999), no. 3, 362\u2013394.","journal-title":"J. Assoc. Comput. Mach."},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory 10 (1977), 99\u2013127.","journal-title":"Math. Syst. Theory"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"U. Zwick. Exact and approximate distances in graphs-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","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T07:06:21Z","timestamp":1556435181000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}