{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:14:39Z","timestamp":1759666479777},"reference-count":60,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":6446,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1016\/0004-3702(94)00047-6","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T02:20:38Z","timestamp":1027650038000},"page":"241-292","source":"Crossref","is-referenced-by-count":45,"title":["Performance of linear-space search algorithms"],"prefix":"10.1016","volume":"79","author":[{"given":"Weixiong","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Richard E.","family":"Korf","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0004-3702(94)00047-6_BIB1","series-title":"The Traveling Salesman Problem","first-page":"361","article-title":"Branch and bound methods","author":"Balas","year":"1985"},{"key":"10.1016\/0004-3702(94)00047-6_BIB2","author":"Binmore","year":"1982"},{"key":"10.1016\/0004-3702(94)00047-6_BIB3","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0004-3702(89)90010-6","article-title":"Heuristic search in restricted memory","volume":"41","author":"Chakrabarti","year":"1989","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB4","series-title":"Proceedings IJCAI-91","first-page":"331","article-title":"Where the really hard problems are","author":"Cheeseman","year":"1991"},{"key":"10.1016\/0004-3702(94)00047-6_BIB5","series-title":"Proceedings AAAI-93","first-page":"21","article-title":"Experimental results on the crossover point in satisfiability problems","author":"Crawford","year":"1993"},{"key":"10.1016\/0004-3702(94)00047-6_BIB6","article-title":"A probabilistic analysis of branch-and-bound search","author":"Dechter","year":"1981"},{"key":"10.1016\/0004-3702(94)00047-6_BIB7","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/3828.3830","article-title":"Generalized best-first search strategies and the optimality of A\u2217","volume":"32","author":"Dechter","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/0004-3702(94)00047-6_BIB8","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":"1971","journal-title":"Numer. Math."},{"key":"10.1016\/0004-3702(94)00047-6_BIB9","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4064\/aa-21-1-399-408","article-title":"On a linear diophantine problem of frobenius","volume":"21","author":"Erd\u00f6s","year":"1972","journal-title":"Acta Arithmatica"},{"key":"10.1016\/0004-3702(94)00047-6_BIB10","article-title":"Analysis of the alpha-beta pruning algorithm","author":"Fuller","year":"1973"},{"key":"10.1016\/0004-3702(94)00047-6_BIB11","author":"Garey","year":"1979"},{"key":"10.1016\/0004-3702(94)00047-6_BIB12","series-title":"Tech. Report CMU-CS-79-124","article-title":"Performance measurement and analysis of certain search algorithms","author":"Gaschnig","year":"1979"},{"key":"10.1016\/0004-3702(94)00047-6_BIB13","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0004-3702(92)90059-7","article-title":"Iterative broadening","volume":"55","author":"Ginsberg","year":"1992","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB14","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1214\/aop\/1176996611","article-title":"Postulates for subadditive processes","volume":"2","author":"Hammersley","year":"1974","journal-title":"Ann. Probability"},{"key":"10.1016\/0004-3702(94)00047-6_BIB15","author":"Harris","year":"1963"},{"key":"10.1016\/0004-3702(94)00047-6_BIB16","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"10.1016\/0004-3702(94)00047-6_BIB17","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(87)90033-6","article-title":"Phase transitions in artificial intelligence systems","volume":"33","author":"Huberman","year":"1987","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB18","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0004-3702(80)90045-4","article-title":"Probabilistic analysis of the complexity of A\u2217","volume":"15","author":"Huyn","year":"1980","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB19","article-title":"Enumerative Approaches to Combinatorial Optimization\u2014Part I","volume":"10","author":"Ibaraki","year":"1987"},{"key":"10.1016\/0004-3702(94)00047-6_BIB20","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0004-3702(83)80006-X","article-title":"Searching for an optimal path in a tree with random costs","volume":"21","author":"Karp","year":"1983","journal-title":"Artif Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB21","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1214\/aop\/1176996266","article-title":"The first birth problem for an age-dependent branching process","volume":"3","author":"Kingman","year":"1975","journal-title":"Ann. Probability"},{"key":"10.1016\/0004-3702(94)00047-6_BIB22","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","article-title":"Depth-first iterative-deepening: An optimal admissible tree search","volume":"27","author":"Korf","year":"1985","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB23","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0004-3702(90)90054-4","article-title":"Real-time heuristic search","volume":"42","author":"Korf","year":"1990","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0004-3702(93)90045-D","article-title":"Linear-space best-first search","volume":"62","author":"Korf","year":"1993","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB25","series-title":"Encyclopedia of Artificial Intelligence","first-page":"1468","article-title":"Search branch-and-bound","author":"Kumar","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB26","series-title":"Search in Artificial Intelligence","first-page":"91","article-title":"A general branch-and-bound formulation for and\/or graph and game tree search","author":"Kumar","year":"1988"},{"key":"10.1016\/0004-3702(94)00047-6_BIB27","series-title":"Proceedings first International Conference on AI Planning Systems","first-page":"145","article-title":"Systematic and nonsystematic search strategies","author":"Langley","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB28","series-title":"Working Notes of AAAI 1993 Spring Symposium: AI and NP-Hard Problems","first-page":"112","article-title":"Evidence for a satisfiability threshold for random 3CNF formulas","author":"Larrabee","year":"1993"},{"key":"10.1016\/0004-3702(94)00047-6_BIB29","author":"Lawler","year":"1985"},{"key":"10.1016\/0004-3702(94)00047-6_BIB30","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/opre.14.4.699","article-title":"Branch-and-bound methods: a survey","volume":"14","author":"Lawler","year":"1966","journal-title":"Operations Research"},{"key":"10.1016\/0004-3702(94)00047-6_BIB31","series-title":"Proceedings AAAI-92","first-page":"539","article-title":"Performance of IDA\u2217 on trees and graphs","author":"Mahanti","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB32","series-title":"Disorder in Physical Systems","first-page":"249","article-title":"Probabilistic analysis of tree search","author":"McDiarmid","year":"1990"},{"key":"10.1016\/0004-3702(94)00047-6_BIB33","series-title":"Proceedings IJCAI-91","first-page":"172","article-title":"An expected-cost analysis of backtracking and non-backtracking algorithms","author":"McDiarmid","year":"1991"},{"key":"10.1016\/0004-3702(94)00047-6_BIB34","series-title":"Proceedings AAAI-92","first-page":"459","article-title":"Hard and easy distributions of SAT problems","author":"Mitchell","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB35","author":"Niven","year":"1980"},{"key":"10.1016\/0004-3702(94)00047-6_BIB36","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0004-3702(94)00047-6_BIB37","article-title":"An analysis of iterative-deepening-A\u2217","author":"Patrick","year":"1991"},{"key":"10.1016\/0004-3702(94)00047-6_BIB38","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01543478","article-title":"An upper bound on the complexity of iterative-deepening-A\u2217","volume":"5","author":"Patrick","year":"1992","journal-title":"Ann. Math. Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB39","author":"Pearl","year":"1984"},{"key":"10.1016\/0004-3702(94)00047-6_BIB40","series-title":"Encyclopedia of Artificial Intelligence","first-page":"127","article-title":"Branching factor","author":"Pearl","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB41","first-page":"55","article-title":"Practical and theoretical considerations in heuristic search algorithms","volume":"8","author":"Pohl","year":"1977"},{"key":"10.1016\/0004-3702(94)00047-6_BIB42","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0004-3702(83)80007-1","article-title":"Search rearrangement backtracking and polynomial average time","volume":"21","author":"Purdom","year":"1983","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB43","series-title":"Proceedings AAAI-86","first-page":"168","article-title":"Finding a shortest solution for the n \u00d7 n extension of the 15-puzzle is intractable","author":"Ratner","year":"1986"},{"key":"10.1016\/0004-3702(94)00047-6_BIB44","author":"R\u00e9nyi","year":"1970"},{"key":"10.1016\/0004-3702(94)00047-6_BIB45","series-title":"Proceedings ECAI-92","article-title":"Efficient memory-bounded search methods","author":"Russell","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB46","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0004-3702(91)90100-X","article-title":"Reducing reexpansions in iterative-deepening search by controlling cutoff bounds","volume":"50","author":"Sarkar","year":"1991","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(94)00047-6_BIB47","series-title":"Proceedings IJCAI-89","first-page":"297","article-title":"Fast recursive formulations for best-first search that allow controlled use of memory","author":"Sen","year":"1989"},{"key":"10.1016\/0004-3702(94)00047-6_BIB48","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/2422.322422","article-title":"Random trees and the analysis of branch and bound procedures","volume":"31","author":"Smith","year":"1984","journal-title":"J. ACM"},{"key":"10.1016\/0004-3702(94)00047-6_BIB49","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1147\/rd.303.0242","article-title":"The average complexity of depth-first search with backtracking and cutoff","volume":"30","author":"Stone","year":"1986","journal-title":"IBM J. Research Development"},{"key":"10.1016\/0004-3702(94)00047-6_BIB50","series-title":"Proceedings AAAI-93","first-page":"756","article-title":"Pruning duplicate nodes in depth-first search","author":"Taylor","year":"1993"},{"key":"10.1016\/0004-3702(94)00047-6_BIB51","series-title":"Proceedings AAAI-91","first-page":"434","article-title":"Depth-first vs best-first search","author":"Vempaty","year":"1991"},{"key":"10.1016\/0004-3702(94)00047-6_BIB52","article-title":"MIDA\u2217, an IDA\u2217 search with dynamic control","author":"Wah","year":"1991"},{"key":"10.1016\/0004-3702(94)00047-6_BIB53","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1109\/TSE.1985.232550","article-title":"Stochastic modeling of branch-and-bound algorithms with best-first search","volume":"11","author":"Wah","year":"1985","journal-title":"IEEE Trans. Software Engineering"},{"key":"10.1016\/0004-3702(94)00047-6_BIB54","series-title":"Proceedings AAAI-93","first-page":"152","article-title":"Extending deep structure","author":"Williams","year":"1993"},{"key":"10.1016\/0004-3702(94)00047-6_BIB55","series-title":"Working Notes of AAAI 1993 Spring Symposium: AI and NP-Hard Problems","first-page":"160","article-title":"Truncated branch-and-bound: a case study on the asymmetric TSP","author":"Zhang","year":"1993"},{"key":"10.1016\/0004-3702(94)00047-6_BIB56","article-title":"Analyses of linear-space search algorithms and applications","author":"Zhang","year":"1994"},{"key":"10.1016\/0004-3702(94)00047-6_BIB57","series-title":"Proceedings AAAI-92","first-page":"545","article-title":"An average-case analysis of branch-and-bound with applications: summary of results","author":"Zhang","year":"1992"},{"key":"10.1016\/0004-3702(94)00047-6_BIB58","series-title":"Proceedings AAAI-93","first-page":"769","article-title":"Depth-first vs. best-first search: New results","author":"Zhang","year":"1993"},{"key":"10.1016\/0004-3702(94)00047-6_BIB59","article-title":"Epsilon-transformation: Exploiting phase transitions to solve combinatorial optimization problems","author":"Zhang","year":"1994"},{"key":"10.1016\/0004-3702(94)00047-6_BIB60","series-title":"Proceedings AAAI-94","article-title":"Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems\u2014initial results","author":"Zhang","year":"1994"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370294000476?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0004370294000476?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T18:54:24Z","timestamp":1555268064000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0004370294000476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["0004370294000476"],"URL":"https:\/\/doi.org\/10.1016\/0004-3702(94)00047-6","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}