{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T06:12:19Z","timestamp":1744697539713},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540439776"},{"type":"electronic","value":"9783540456438"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45643-0_10","type":"book-chapter","created":{"date-parts":[[2007,9,25]],"date-time":"2007-09-25T00:58:33Z","timestamp":1190681913000},"page":"126-142","source":"Crossref","is-referenced-by-count":20,"title":["Experimental Evaluation of a New Shortest Path Algorithm"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srinath","family":"Sridhar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,7,12]]},"reference":[{"key":"10_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"10_CR2","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s. Random Graphs. Academic Press, London, 1985."},{"key":"10_CR3","first-page":"129","volume":"73","author":"B. V. Cherkassky","year":"1996","unstructured":"B. V. Cherkassky, A. V. Goldberg, T. Radzik. Shortest paths algorithms: Theory and experimental evaluation. In Math. Prog. 73 (1996), 129\u2013174.","journal-title":"Math. Prog."},{"key":"10_CR4","unstructured":"T. Cormen, C. Leiserson, R. Rivest. Intro. to Algorithms. MIT Press, 1990."},{"key":"10_CR5","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":"10_CR6","first-page":"343","volume":"38","author":"P. Erd\u00f6s","year":"1961","unstructured":"P. Erd\u00f6s, A. R\u00e9nyi On the evolution of random graphs. Bull. Inst. Internat. Statist. 38, pp. 343\u2013347, 1961.","journal-title":"Bull. Inst. Internat. Statist"},{"key":"10_CR7","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":"10_CR8","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M. L. Fredman","year":"1986","unstructured":"M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan. The pairing heap: A new form of self-adjusting heap. In Algorithmica 1 (1986) pp. 111\u2013129.","journal-title":"Algorithmica"},{"key":"10_CR9","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":"10_CR10","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":"10_CR11","doi-asserted-by":"crossref","unstructured":"A. Goldberg. A simple shortest path algorithm with linear average time. InterTrust Technical Report STAR-TR-01-03, March 2001.","DOI":"10.1007\/3-540-44676-1_19"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"A. Goldberg. Shortest path algorithms: engineering aspects. ISSAC 2001.","DOI":"10.1007\/3-540-45678-3_43"},{"key":"10_CR13","unstructured":"A. Goldberg, C. Silverstein. Implementations of Dijkstra\u2019s algorithm based on multi-level buckets. Network optimization (1997), Lec. Not. Econ. Math. Syst. 450, 292\u2013327."},{"key":"10_CR14","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":"10_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-44985-X_5","volume-title":"Algorithm theory\u2014SWAT 2000 (Bergen)","author":"J. Iacono","year":"2000","unstructured":"J. Iacono. Improved upper bounds for pairing heaps. Algorithm theory\u2014SWAT 2000 (Bergen), LNCS vol. 1851, 32\u201345"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"H. Jakobsson, Mixed-approach algorithms for transitive closure. In Proc. ACM PODS, 1991, pp. 199\u2013205.","DOI":"10.1145\/113413.113431"},{"key":"10_CR17","first-page":"57","volume":"6","author":"V. Jarn\u00edk","year":"1930","unstructured":"V. Jarn\u00edk, O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ca Moravsk\u00e9 Pr\u00edrodovedeck\u00e9 Spolecnosti 6 (1930), 57\u201363, in Czech.","journal-title":"Pr\u00e1ca Moravsk\u00e9 Pr\u00edrodovedeck\u00e9 Spolecnosti"},{"issue":"6","key":"10_CR18","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":"10_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1006\/jagm.1998.0937","volume":"28","author":"S. Kolliopoulos","year":"1998","unstructured":"S. Kolliopoulos, C. Stein. Finding real-valued single-source shortest paths in o(n 3) expected time. J. Algorithms 28 (1998), no. 1, 125\u2013141.","journal-title":"J. Algorithms"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"C. C. McGeoch. A new all-pairs shortest-path algorithm. Tech. Report 91-30 DIMACS, 1991. Also appears in Algorithmica, 13(5): 426\u2013461, 1995.","DOI":"10.1007\/BF01190847"},{"key":"10_CR21","unstructured":"K. Mehlhorn, S. N\u00e4her. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge Univ. Press, 1999."},{"key":"10_CR22","unstructured":"U. Meyer. Single source shortest paths on arbitrary directed graphs in linear average-case time. In Proc. SODA 2001, 797\u2013806."},{"issue":"6","key":"10_CR23","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1137\/0216065","volume":"16","author":"A. Moffat","year":"1987","unstructured":"A. Moffat, T. Takaoka. An all pairs shortest path algorithm with expected time O(n 2log n). SIAM J. Comput. 16 (1987), no. 6, 1023\u20131031.","journal-title":"SIAM J. Comput."},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"B. M. E. Moret, H. D. Shapiro. An empirical assessment of algorithms for constructing a minimum spanning tree. In DIMACS Series on Discrete Math. and Theor. CS, 1994.","DOI":"10.1090\/dimacs\/015\/09"},{"key":"10_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/3-540-45022-X_6","volume-title":"Proc. ICALP 2000","author":"S. Pettie","year":"2000","unstructured":"S. Pettie, V. Ramachandran. An optimal minimum spanning tree algorithm. In Proc. ICALP 2000, LNCS volume 1853, 49\u201360. JACM, to appear."},{"key":"10_CR26","unstructured":"S. Pettie, V. Ramachandran. Computing shortest paths with comparisons and additions. In Proc. SODA\u2019 02, January 2002, to appear."},{"key":"10_CR27","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/351827.384249","volume":"5","author":"P. Sanders","year":"2000","unstructured":"P. Sanders. Fast priority queues for cached memory. J. Experimental Algorithms 5, article 7, 2000.","journal-title":"J. Experimental Algorithms"},{"issue":"4","key":"10_CR28","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":"10_CR29","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":"10_CR30","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/3-540-48224-5_21","volume-title":"Proc. ICALP 2001","author":"M. Thorup","year":"2001","unstructured":"M. Thorup. Quick k-median, k-center, and facility location for sparse graphs. In Proc. ICALP 2001, LNCS Vol. 2076, 249\u2013260."},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"U. Zwick. Exact and approximate distances in graphs \u2014 a survey. In Proc. 9th ESA (2001), 33\u201348. Updated copy at http:\/\/www.cs.tau.ac.il\/~zwick","DOI":"10.1007\/3-540-44676-1_3"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experiments"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45643-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T07:53:44Z","timestamp":1556870024000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45643-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540439776","9783540456438"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-45643-0_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}