{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T17:07:16Z","timestamp":1717520836271},"reference-count":71,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,8,1]],"date-time":"2003-08-01T00:00:00Z","timestamp":1059696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[2003,8]]},"DOI":"10.1016\/s0196-6774(03)00046-4","type":"journal-article","created":{"date-parts":[[2003,6,21]],"date-time":"2003-06-21T00:09:47Z","timestamp":1056154187000},"page":"91-134","source":"Crossref","is-referenced-by-count":25,"title":["Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds"],"prefix":"10.1016","volume":"48","author":[{"given":"Ulrich","family":"Meyer","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0196-6774(03)00046-4_BIB001","series-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja","year":"1993"},{"issue":"2","key":"10.1016\/S0196-6774(03)00046-4_BIB002","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","article-title":"Faster algorithms for the shortest path problem","volume":"37","author":"Ahuja","year":"1990","journal-title":"J. ACM"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB003","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Quart. Appl. Math."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB004","series-title":"Proc. 7th Ann. Symp. on Discrete Algorithms","first-page":"52","article-title":"Worst-case efficient priority queues","author":"Brodal","year":"1996"},{"issue":"3\u20134","key":"10.1016\/S0196-6774(03)00046-4_BIB005","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/s004530010016","article-title":"Shortest paths in digraphs of small treewidth, Part I: Sequential algorithms","volume":"27","author":"Chaudhuri","year":"2000","journal-title":"Algorithmica"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB006","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02592101","article-title":"Shortest path algorithms: Theory and experimental evaluation","volume":"73","author":"Cherkassky","year":"1996","journal-title":"Math. Programming"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB007","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","author":"Chernoff","year":"1952","journal-title":"Ann. Math. Statist."},{"issue":"1","key":"10.1016\/S0196-6774(03)00046-4_BIB008","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/43.673630","article-title":"Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design","volume":"17","author":"Cong","year":"1998","journal-title":"IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB009","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<33::AID-RSA3>3.0.CO;2-0","article-title":"Average-case complexity of shortest-paths problems in the vertex-potential model","volume":"16","author":"Cooper","year":"2000","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB010","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1287\/opre.27.1.161","article-title":"Shortest route methods: 1. Reaching pruning and buckets","volume":"27","author":"Denardo","year":"1979","journal-title":"Oper. Res."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB011","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/net.3230140208","article-title":"Shortest-path algorithms: Taxonomy and annotation","volume":"14","author":"Deo","year":"1984","journal-title":"Networks"},{"issue":"11","key":"10.1016\/S0196-6774(03)00046-4_BIB012","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1145\/363269.363610","article-title":"Algorithm 360: Shortest-path forest with topological ordering","volume":"12","author":"Dial","year":"1969","journal-title":"Commun. ACM"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB013","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/net.3230090304","article-title":"A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees","volume":"9","author":"Dial","year":"1979","journal-title":"Networks"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB014","series-title":"RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science","first-page":"294","article-title":"Random geometric problems on [0,1]2","volume":"1518","author":"D\u0131\u0301az","year":"1998"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB015","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Nummer. Math."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB016","series-title":"Transportation Modeling Systems","first-page":"36","article-title":"Economical algorithms for finding shortest paths in a network","author":"Dinic","year":"1978"},{"issue":"11","key":"10.1016\/S0196-6774(03)00046-4_BIB017","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1145\/50087.50096","article-title":"Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation","volume":"31","author":"Driscoll","year":"1988","journal-title":"Commun. ACM"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB018","unstructured":"D.P. Dubhashi, A. Panconesi, Concentration of measure for the analysis of randomized algorithms, Draft Manuscript, http:\/\/www.brics.dk\/~ale\/papers.html, October 1998"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB019","series-title":"An Introduction to Probability Theory and Its Applications, Vol. I","author":"Feller","year":"1968"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB020","series-title":"An Introduction to Probability Theory and Its Applications, Vol. II","author":"Feller","year":"1971"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB021","series-title":"Flows in Networks","author":"Ford","year":"1963"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB022","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB023","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","article-title":"Surpassing the information theoretic bound with fusion trees","volume":"47","author":"Fredman","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB024","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","article-title":"Trans-dichotomous algorithms for minimum spanning trees and shortest paths","volume":"48","author":"Fredman","year":"1994","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB025","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/BF01580382","article-title":"Shortest path algorithms for knapsack type problems","volume":"11","author":"Frieze","year":"1976","journal-title":"Math. Programming"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB026","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","article-title":"The shortest-path problem for graphs with random arc-lengths","volume":"10","author":"Frieze","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB027","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/BFb0121087","article-title":"Shortest path methods: A unifying approach","volume":"26","author":"Gallo","year":"1986","journal-title":"Math. Programming Study"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB028","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02288320","article-title":"Shortest path algorithms","volume":"13","author":"Gallo","year":"1988","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB029","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230140103","article-title":"Computational study of an improved shortest path algorithm","volume":"14","author":"Glover","year":"1984","journal-title":"Networks"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB030","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/opre.33.1.65","article-title":"A new polynomially bounded shortest path algorithm","volume":"33","author":"Glover","year":"1985","journal-title":"Oper. Res."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB031","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1287\/mnsc.31.9.1106","article-title":"New polynomial shortest path algorithms and their computational attributes","volume":"31","author":"Glover","year":"1985","journal-title":"Management Sci."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB032","series-title":"Proc. 9th Ann. European Symposium on Algorithms (ESA)","first-page":"230","article-title":"A simple shortest path algorithm with linear average time","volume":"2161","author":"Goldberg","year":"2001"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB033","series-title":"Proc. 12th Intern. Symposium on Algorithms and Computation (ISAAC 2001)","first-page":"502","article-title":"Shortest path algorithms: Engineering aspects","volume":"2223","author":"Goldberg","year":"2001"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB034","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0893-9659(93)90022-F","article-title":"A heuristic improvement of the Bellman\u2013Ford algorithm","volume":"6","author":"Goldberg","year":"1993","journal-title":"Appl. Math. Lett."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB035","unstructured":"A.V. Goldberg, R.E. Tarjan, Expected performance of Dijkstra's shortest path algorithm, Technical Report TR-96-062, NEC Research, 1996"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB036","series-title":"Studies in Operations Management","first-page":"365","article-title":"Transportation planning: Network models and their implementation","author":"Golden","year":"1978"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB037","series-title":"Probability and Random Processes","author":"Grimmett","year":"2001"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB038","series-title":"27th Colloquium on Automata, Languages and Programming (ICALP)","first-page":"61","article-title":"Improved shortest paths on the word RAM","volume":"1853","author":"Hagerup","year":"2000"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB039","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","article-title":"A guided tour of Chernoff bounds","volume":"33","author":"Hagerup","year":"1990","journal-title":"Inform. Proc. Lett."},{"issue":"4","key":"10.1016\/S0196-6774(03)00046-4_BIB040","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1287\/moor.10.4.557","article-title":"On shortest paths in graphs with random weights","volume":"10","author":"Hassin","year":"1985","journal-title":"Math. Oper. Res."},{"issue":"1","key":"10.1016\/S0196-6774(03)00046-4_BIB041","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","article-title":"Faster shortest-path algorithms for planar graphs","volume":"55","author":"Henzinger","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB042","doi-asserted-by":"crossref","first-page":"13","DOI":"10.2307\/2282952","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1964","journal-title":"J. Amer. Statist. Assoc."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB043","first-page":"94","article-title":"The traveling salesman problem as a constrained shortest path problem: Theory and computation experience","volume":"17","author":"Houck","year":"1980","journal-title":"Opsearch (India)"},{"issue":"6","key":"10.1016\/S0196-6774(03)00046-4_BIB044","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0305-0548(88)90052-4","article-title":"A computational study of efficient shortest path algorithms","volume":"15","author":"Hung","year":"1988","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB045","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<205::AID-RSA11>3.0.CO;2-7","article-title":"On the all-pairs shortest-path algorithm of Moffat and Takaoka","volume":"10","author":"Mehlhorn","year":"1997","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB046","series-title":"Proc. 12th Ann. Symp. on Discrete Algorithms","first-page":"797","article-title":"Single-source shortest-paths on arbitrary directed graphs in linear average-case time","author":"Meyer","year":"2001"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB047","unstructured":"U. Meyer, Design and analysis of sequential and parallel single-source shortest-paths algorithms, PhD thesis, Universit\u00e4t des Saarlandes, 2002"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB048","series-title":"Proc. 6th Ann. European Symposium on Algorithms (ESA)","first-page":"393","article-title":"\u0394-stepping: A parallel single source shortest path algorithm","volume":"1461","author":"Meyer","year":"1998"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB049","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1137\/0216065","article-title":"An all pairs shortest path algorithm with expected time O(n2logn)","volume":"16","author":"Moffat","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB050","doi-asserted-by":"crossref","DOI":"10.1016\/0305-0548(91)90014-I","article-title":"Shortest path algorithms: A computational study with the C programming language","volume":"18","author":"Mondou","year":"1991","journal-title":"Comput. Oper. Res."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB051","series-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB052","unstructured":"M. Nonato, S. Pallottino, B. Xuewen, SPT_L shortest path algorithms: Review, new proposals and some experimental results. Technical Report TR-99-16, University of Pisa, Department of Computer Science, 1999"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB053","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1016\/0196-6774(85)90009-4","article-title":"A theorem on the expected complexity of Dijkstra's shortest path algorithm","volume":"6","author":"Noshita","year":"1985","journal-title":"J. Algorithms"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB054","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1002\/net.3230140206","article-title":"Shortest-path methods: Complexity, interrelations and new propositions","volume":"14","author":"Pallottino","year":"1984","journal-title":"Networks"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB055","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/BF01585517","article-title":"Implementation and efficiency of Moore-algorithms for the shortest route problem","volume":"7","author":"Pape","year":"1974","journal-title":"Math. Programming"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB056","series-title":"Proc. 13th Ann. Symp. on Discrete Algorithms","first-page":"267","article-title":"Computing shortest paths with comparisons and additions","author":"Pettie","year":"2002"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB057","series-title":"4th Annual European Symposium on Algorithms (ESA)","first-page":"121","article-title":"Priority queues: Small, monotone and trans-dichotomous","volume":"1136","author":"Raman","year":"1996"},{"issue":"2","key":"10.1016\/S0196-6774(03)00046-4_BIB058","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/261342.261352","article-title":"Recent results on the single-source shortest paths problem","volume":"28","author":"Raman","year":"1997","journal-title":"ACM SIGACT News"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB059","article-title":"Probabilistic Methods for Coordination Problems","volume":"78","author":"Scheideler","year":"2000"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB060","series-title":"IEEE Transactions on Communications","first-page":"539","article-title":"Routing techniques used in computer communication networks","author":"Schwartz","year":"1980"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB061","series-title":"An introduction to the analysis of algorithms","author":"Sedgewick","year":"1996"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB062","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF01840435","article-title":"Shortest paths in Euclidean graphs","volume":"1","author":"Sedgewick","year":"1986","journal-title":"Algorithmica"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB063","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0202004","article-title":"A new algorithm for finding all shortest paths in a graph of positive arcs in average time O(n2log2n)","volume":"2","author":"Spira","year":"1973","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB064","series-title":"Computing and Combinatorics","first-page":"41","article-title":"Theory of 2\u20133 heaps","volume":"1627","author":"Takaoka","year":"1999"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB065","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1145\/316542.316548","article-title":"Undirected single-source shortest paths with positive integer weights in linear time","volume":"46","author":"Thorup","year":"1999","journal-title":"J. ACM"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB066","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1006\/jagm.2000.1080","article-title":"Floats, integers, and single source shortest paths","volume":"35","author":"Thorup","year":"2000","journal-title":"J. Algorithms"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB067","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1137\/S0097539795288246","article-title":"On RAM priority queues","volume":"30","author":"Thorup","year":"2000","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB068","series-title":"Mathematical Methods for DNA Sequences","author":"Waterman","year":"1988"},{"issue":"6","key":"10.1016\/S0196-6774(03)00046-4_BIB069","first-page":"347","article-title":"Heapsort","volume":"7","author":"Williams","year":"1964","journal-title":"Commun. ACM"},{"key":"10.1016\/S0196-6774(03)00046-4_BIB070","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/trsc.32.1.65","article-title":"Shortest path algorithms: An evaluation using real road networks","volume":"32","author":"Zhan","year":"1998","journal-title":"Transportation Sci."},{"key":"10.1016\/S0196-6774(03)00046-4_BIB071","series-title":"Proc. 9th Ann. European Symposium on Algorithms (ESA)","first-page":"33","article-title":"Exact and approximate distances in graphs\u2014a survey","volume":"2161","author":"Zwick","year":"2001"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677403000464?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677403000464?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T06:24:40Z","timestamp":1553063080000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677403000464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["S0196677403000464"],"URL":"https:\/\/doi.org\/10.1016\/s0196-6774(03)00046-4","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}