{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:31Z","timestamp":1725665071488},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:22:26Z","timestamp":1330298546000},"page":"15-26","source":"Crossref","is-referenced-by-count":3,"title":["Average-case complexity of shortest-paths problems in the vertex-potential model"],"prefix":"10.1007","author":[{"given":"Colin","family":"Cooper","sequence":"first","affiliation":[]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[]},{"given":"Volker","family":"Priebe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"R. K. Ahuja","year":"1990","unstructured":"R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan, Faster algorithms for the shortest path problem, J. Assoc. Comput. Mach.\n37 (1990) 213\u2013223","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"R. Bellman, On a routing problem, Quart. Appl. Math.\n16 (1958) 87\u201390","journal-title":"Quart. Appl. Math."},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1137\/0212039","volume":"12","author":"P. A. Bloniarz","year":"1983","unstructured":"P. A. Bloniarz, A shortest-path algorithm with expected time O(n\n2 log n log *\nn), SIAM J. Comput.\n12 (1983) 588\u2013600","journal-title":"SIAM J. Comput."},{"key":"2_CR4","first-page":"129","volume":"73","author":"B. V. Cherkassky","year":"1996","unstructured":"B. V. Cherkassky, A. V. Goldberg, and T. Radzik, Shortest paths algorithms: Theory and experimental evaluation, Math. Programming\n73 (1996) 129\u2013174","journal-title":"Math. Programming"},{"key":"2_CR5","unstructured":"B. V. Cherkassky, A. V. Goldberg, and C. Silverstein, Buckets, heaps, lists, and monotone priority queues, Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans LA, 1997, 83\u201392"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(93)90059-I","volume":"46","author":"R. Davis","year":"1993","unstructured":"R. Davis and A. Prieditis, The expected length of a shortest path, Inform. Process. Lett.\n46 (1993) 135\u2013141","journal-title":"Inform. Process. Lett."},{"key":"2_CR7","doi-asserted-by":"crossref","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, Numer. Math.\n1 (1959) 269\u2013271","journal-title":"Numer. Math."},{"key":"2_CR8","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. Assoc. Comput. Mach.\n19 (1972) 248\u2013264","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR9","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton NJ, 1962"},{"key":"2_CR10","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach.\n34 (1987) 596\u2013615","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A. M. Frieze","year":"1985","unstructured":"A. M. Frieze and G. R. Grimmett, The shortest-path problem for graphs with random arc-lengths, Discrete Appl. Math.\n10 (1985) 57\u201377","journal-title":"Discrete Appl. Math."},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"A. V. Goldberg","year":"1995","unstructured":"A. V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM J. Comput.\n24 (1995) 494\u2013504","journal-title":"SIAM J. Comput."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1989\/90","unstructured":"T. Hagerup and C. R\u00fcb, A guided tour of Chernoff bounds, Inform. Process. Lett.\n33 (1989\/90) 305\u2013308","journal-title":"Inform. Process. Lett."},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1287\/moor.10.4.557","volume":"10","author":"R. Hassin","year":"1985","unstructured":"R. Hassin and E. Zemel, On shortest paths in graphs with random weights, Math. Oper. Res.\n10 (1985) 557\u2013564","journal-title":"Math. Oper. Res."},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc.\n58 (1963) 13\u201330","journal-title":"J. Amer. Statist. Assoc."},{"key":"2_CR16","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.\n24 (1977) 1\u201313","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1137\/0222071","volume":"22","author":"D. R. Karger","year":"1993","unstructured":"D. R. Karger, D. Koller, and S. J. Phillips, Finding the hidden path: Time bounds for all-pairs shortest paths, SIAM J. Comput.\n22 (1993) 1199\u20131217","journal-title":"SIAM J. Comput."},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science; 1084","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-61310-2_8","volume-title":"Integer Programming and Combinatorial Optimization","author":"S. G. Kolliopoulos","year":"1996","unstructured":"S. G. Kolliopoulos and C. Stein, Finding real-valued single-source shortest paths in o(n\n3) expected time, in: W. H. Cunningham, S. T. McCormick, and M. Queyranne (Eds.), Integer Programming and Combinatorial Optimization (Lecture Notes in Computer Science; 1084), Springer-Verlag, Berlin, 1996, 94\u2013104"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/BF01190847","volume":"13","author":"C. C. McGeoch","year":"1995","unstructured":"C. C. McGeoch, All-pairs shortest paths and the essential subgraph, Algorithmica\n13 (1995) 426\u2013441","journal-title":"Algorithmica"},{"key":"2_CR20","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","volume":"10","author":"K. Mehlhorn","year":"1997","unstructured":"K. Mehlhorn and V. Priebe, On the all-pairs shortest-path algorithm of Moffat and Takaoka, Random Structures Algorithms\n10 (1997) 205\u2013220","journal-title":"Random Structures Algorithms"},{"key":"2_CR21","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1137\/0216065","volume":"16","author":"A. Moffat","year":"1987","unstructured":"A. Moffat and T. Takaoka, An all pairs shortest path algorithm with expected time O(n\n2 log n), SIAM J. Comput.\n16 (1987) 1023\u20131031","journal-title":"SIAM J. Comput."},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1016\/0196-6774(85)90009-4","volume":"6","author":"K. Noshita","year":"1985","unstructured":"K. Noshita, A theorem on the expected complexity of Dijkstra's shortest path algorithm, J. Algorithms\n6 (1985) 400\u2013408","journal-title":"J. Algorithms"},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0202004","volume":"2","author":"P. M. Spira","year":"1973","unstructured":"P. M. Spira, A new algorithm for finding all shortest paths in a graph of positive arcs in average time O(n\n2 log2\nn), SIAM J. Comput.\n2 (1973) 28\u201332","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:43:21Z","timestamp":1619574201000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}