{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T04:22:23Z","timestamp":1773462143492,"version":"3.50.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1989,6,1]],"date-time":"1989-06-01T00:00:00Z","timestamp":612662400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1989,6]]},"DOI":"10.1007\/bf01553908","type":"journal-article","created":{"date-parts":[[2005,4,20]],"date-time":"2005-04-20T22:07:35Z","timestamp":1114034855000},"page":"551-567","source":"Crossref","is-referenced-by-count":33,"title":["A bidirectional shortest-path algorithm with good average-case behavior"],"prefix":"10.1007","volume":"4","author":[{"given":"Michael","family":"Luby","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01553908_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. A. Aho","year":"1974","unstructured":"Aho, A. A., Hopcroft, J. E., and Ullman, J. D.The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974."},{"key":"BF01553908_CR2","doi-asserted-by":"crossref","unstructured":"Balas, E., and Toth, P. Branch and Bound Methods for the Traveling Salesman Problem, MSRR 488, Carnegie-Mellon University, March 1983.","DOI":"10.21236\/ADA126957"},{"key":"BF01553908_CR3","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"Bollob\u00e1s, B.Random Graphs. Academic Press, New York, 1985."},{"key":"BF01553908_CR4","first-page":"260","volume":"l","author":"E. W. Dijkstra","year":"1959","unstructured":"Dijkstra, E. W. A Note on Two Problems in Connection with Graphs,Numerische Mathematik,l (1959), 260\u2013271.","journal-title":"Numerische Mathematik"},{"key":"BF01553908_CR5","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., and Karp, R. M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems,Journal of the ACM,19 (1972), 248\u2013264.","journal-title":"Journal of the ACM"},{"key":"BF01553908_CR6","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"Lawler, E. L.Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976."},{"key":"BF01553908_CR7","unstructured":"Ma, Y. A Shortest Path Algorithm with Expected Running TimeO(\u221aV log V), Master's Project Report, University of California, Berkeley."},{"key":"BF01553908_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-99970-3","volume-title":"Analytic Inequalities","author":"D. S. Mitrinovic","year":"1970","unstructured":"Mitrinovic, D. S.Analytic Inequalities. Springer-Verlag, Berlin, 1970."},{"key":"BF01553908_CR9","unstructured":"Perl, Y. Average Analysis of Simple Path Algorithms, Tech. Report UIUCDCS-R-77-905, University of Illinois at Urbana-Champaign, 1977."},{"key":"BF01553908_CR10","first-page":"127","volume":"6","author":"I. Pohl","year":"1971","unstructured":"Pohl, I. Bidirectional Search,Machine Intelligence,6 (1971), 127\u2013140.","journal-title":"Machine Intelligence"},{"key":"BF01553908_CR11","volume-title":"Probability Theory","author":"A. Renyi","year":"1970","unstructured":"Renyi, A.Probability Theory. North-Holland, Amsterdam, 1970."},{"key":"BF01553908_CR12","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0202004","volume":"2","author":"P. M. Spira","year":"1973","unstructured":"Spira, P. M. A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average TimeO(n 2log2 n),SIAM Journal of Computing,2 (1973), 28\u201332.","journal-title":"SIAM Journal of Computing"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553908.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01553908\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T01:16:35Z","timestamp":1586222195000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01553908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,6]]},"references-count":12,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1989,6]]}},"alternative-id":["BF01553908"],"URL":"https:\/\/doi.org\/10.1007\/bf01553908","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,6]]}}}