{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T08:53:39Z","timestamp":1760345619413},"reference-count":56,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1993,4,1]],"date-time":"1993-04-01T00:00:00Z","timestamp":733622400000},"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":["Artificial Intelligence"],"published-print":{"date-parts":[[1993,4]]},"DOI":"10.1016\/0004-3702(93)90002-s","type":"journal-article","created":{"date-parts":[[2003,3,14]],"date-time":"2003-03-14T13:02:52Z","timestamp":1047646972000},"page":"199-242","source":"Crossref","is-referenced-by-count":31,"title":["Depth-first heuristic search on a SIMD machine"],"prefix":"10.1016","volume":"60","author":[{"given":"Curt","family":"Powley","sequence":"first","affiliation":[]},{"given":"Chris","family":"Ferguson","sequence":"additional","affiliation":[]},{"given":"Richard E.","family":"Korf","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0004-3702(93)90002-S_BIB1","series-title":"Proceedings Third IEEE Symposium on the Frontiers of Massively Parallel Computation","article-title":"Efficient parallel algorithms for search problems: applications in VLSI CAD","author":"Arvindam","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB2","article-title":"The design and analysis of algorithms for asynchronous multiprocessors","author":"Baudet","year":"1978"},{"issue":"2","key":"10.1016\/0004-3702(93)90002-S_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(93)90002-S_BIB4","article-title":"Programming the Connection Machine","author":"Christman","year":"1983"},{"key":"10.1016\/0004-3702(93)90002-S_BIB5","series-title":"Connection Machine Model CM-2 technical summary","year":"1989"},{"issue":"3","key":"10.1016\/0004-3702(93)90002-S_BIB6","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(93)90002-S_BIB7","author":"Ebeling","year":"1987"},{"key":"10.1016\/0004-3702(93)90002-S_BIB8","series-title":"Proceedings Third IEEE Symposium on the Frontiers of Massively Parallel Computations","first-page":"145","article-title":"PRA\u2217: a memory-limited heuristic search procedure for the Connection Machine","author":"Evett","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB9","unstructured":"M. Evett, Personal communication (1992)."},{"key":"10.1016\/0004-3702(93)90002-S_BIB10","series-title":"Parallel Algorithms for Machine Intelligence and Vision","first-page":"66","article-title":"Distributed game tree search","author":"Feldmann","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB11","series-title":"Proceedings International Conference on Fifth Generation Computer Systems","article-title":"A highly parallel chess program","author":"Felten","year":"1988"},{"key":"10.1016\/0004-3702(93)90002-S_BIB12","series-title":"Proceedings AAAI-88","first-page":"128","article-title":"Distributed tree search and its application to alpha-beta pruning","author":"Ferguson","year":"1988"},{"issue":"2","key":"10.1016\/0004-3702(93)90002-S_BIB13","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/22719.24067","article-title":"DIB\u2014a distributed implementation of backtracking","volume":"9","author":"Finkel","year":"1987","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"10.1016\/0004-3702(93)90002-S_BIB14","unstructured":"R. Frye, Personal communication (1992)."},{"key":"10.1016\/0004-3702(93)90002-S_BIB15","article-title":"Exhaustive search of unstructured trees on the Connection Machine","author":"Frye","year":"1990","journal-title":"Thinking Machines Corporation Tech. Rept. TMC-196"},{"key":"10.1016\/0004-3702(93)90002-S_BIB16","series-title":"Proceedings Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","first-page":"50","article-title":"A multi-level load balancing scheme for or-parallel exhaustive search programs on the multi-psi","author":"Furuichi","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB17","series-title":"Proceedings AAAI-90","first-page":"216","article-title":"Iterative broadening","author":"Ginsberg","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB18","series-title":"Proceedings Conference on Parallel Computing","article-title":"Experimental evaluation of load balancing techniques for the hypercube","author":"Grama","year":"1991"},{"issue":"2","key":"10.1016\/0004-3702(93)90002-S_BIB19","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(93)90002-S_BIB20","author":"Hillis","year":"1986"},{"issue":"4","key":"10.1016\/0004-3702(93)90002-S_BIB21","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1038\/scientificamerican1090-44","article-title":"A Grandmaster Chess Machine","volume":"263","author":"Hsu","year":"1990","journal-title":"Sci. Am."},{"key":"10.1016\/0004-3702(93)90002-S_BIB22","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/0004-3702(93)90002-S_BIB23","series-title":"Proceedings 20th Annual ACM Symposium on Theory of Computing","first-page":"290","article-title":"A randomized parallel branch-and-bound procedure","author":"Karp","year":"1988"},{"key":"10.1016\/0004-3702(93)90002-S_BIB24","author":"Kleinrock","year":"1975"},{"issue":"1","key":"10.1016\/0004-3702(93)90002-S_BIB25","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(93)90002-S_BIB26","article-title":"Linear-space best-first search","volume":"61","author":"Korf","year":"1993","journal-title":"Artif. Intell."},{"issue":"6","key":"10.1016\/0004-3702(93)90002-S_BIB27","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/BF01389001","article-title":"Parallel depth-first search, Part II: analysis","volume":"16","author":"Kumar","year":"1987","journal-title":"Int. J. Parallel Program."},{"key":"10.1016\/0004-3702(93)90002-S_BIB28","article-title":"Scalable load balancing techniques for parallel computers","author":"Kumar","year":"1991"},{"key":"10.1016\/0004-3702(93)90002-S_BIB29","series-title":"Proceedings First International Conference on AI Planning Systems","article-title":"Systematic and nonsystematic search strategies","author":"Langley","year":"1992"},{"key":"10.1016\/0004-3702(93)90002-S_BIB30","series-title":"Proceedings Sixth International Parallel Processing Symposium","first-page":"543","article-title":"Load balancing for distributed branch and bound algorithms","author":"L\u00fcling","year":"1992"},{"key":"10.1016\/0004-3702(93)90002-S_BIB31","series-title":"Proceedings Third IEEE Symposium on Parallel and Distributed Processing","first-page":"686","article-title":"Load balancing in large networks: a comparative study","author":"L\u00fcling","year":"1991"},{"key":"10.1016\/0004-3702(93)90002-S_BIB32","unstructured":"A. Mahanti, Personal communication (1991)."},{"key":"10.1016\/0004-3702(93)90002-S_BIB33","unstructured":"A. Mahanti, Personal communication (1992)."},{"key":"10.1016\/0004-3702(93)90002-S_BIB34","series-title":"Proceedings Sixth International Parallel Processing Symposium","first-page":"220","article-title":"IDPS: a massively parallel heuristic search algorithm","author":"Mahanti","year":"1992"},{"issue":"2","key":"10.1016\/0004-3702(93)90002-S_BIB35","doi-asserted-by":"crossref","DOI":"10.1016\/0004-3702(93)90003-T","article-title":"A SIMD approach to parallel heuristic search","volume":"60","author":"Mahanti","year":"1993","journal-title":"Artif. Intell."},{"key":"10.1016\/0004-3702(93)90002-S_BIB36","article-title":"Probabilistic performance analysis of heuristic search using parallel hash tables","author":"Manzini","year":"1992"},{"issue":"9","key":"10.1016\/0004-3702(93)90002-S_BIB37","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1109\/12.2258","article-title":"Dynamic remapping of parallel computations with varying resource demands","volume":"37","author":"Nicol","year":"1988","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"10.1016\/0004-3702(93)90002-S_BIB38","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1109\/43.46806","article-title":"A parallel branch and bound algorithm for test generation","volume":"9","author":"Patil","year":"1990","journal-title":"IEEE Trans. Comput. Aided Des."},{"key":"10.1016\/0004-3702(93)90002-S_BIB39","author":"Pearl","year":"1984"},{"key":"10.1016\/0004-3702(93)90002-S_BIB40","series-title":"Parallel Algorithms for Machine Intelligence and Vision","first-page":"42","article-title":"Parallel heuristic search: two approaches","author":"Powley","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB41","series-title":"Proceedings Third IEEE Symposium on Parallel and Distributed Processing","first-page":"249","article-title":"Parallel tree search on a SIMD machine","author":"Powley","year":"1991"},{"key":"10.1016\/0004-3702(93)90002-S_BIB42","series-title":"Proceedings AAAI Spring Symposium on Planning and Search","first-page":"49","article-title":"SIMD and MIMD parallel search","author":"Powley","year":"1989"},{"key":"10.1016\/0004-3702(93)90002-S_BIB43","series-title":"Proceedings IJCAI-89 Workshop on Parallel Algorithms for Machine Intelligence","article-title":"SIMD parallel search","author":"Powley","year":"1989"},{"issue":"5","key":"10.1016\/0004-3702(93)90002-S_BIB44","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1109\/34.134045","article-title":"Single-agent parallel window search","volume":"13","author":"Powley","year":"1991","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10.1016\/0004-3702(93)90002-S_BIB45","series-title":"Proceedings IJCAI-91 International Workshop on Parallel Processing for Artificial Intelligence","first-page":"161","article-title":"SIMD IDA\u2217: extended abstract","author":"Powley","year":"1991"},{"key":"10.1016\/0004-3702(93)90002-S_BIB46","series-title":"Proceedings Third ACM Symposium on Parallel Algorithms and Architectures","article-title":"Optimal speedup for backtrack search on a butterfly network","author":"Ranade","year":"1991"},{"issue":"6","key":"10.1016\/0004-3702(93)90002-S_BIB47","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/BF01389000","article-title":"Parallel depth-first search, Part I: implementation","volume":"16","author":"Rao","year":"1987","journal-title":"Int. J. Parallel Program."},{"key":"10.1016\/0004-3702(93)90002-S_BIB48","doi-asserted-by":"crossref","unstructured":"V.N. Rao and V. Kumar, On the efficiency of parallel backtracking, IEEE Trans. Parallel Distrib. Syst. (to appear).","DOI":"10.1109\/71.219757"},{"key":"10.1016\/0004-3702(93)90002-S_BIB49","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(93)90002-S_BIB50","series-title":"Proceedings AAAI-90","first-page":"227","article-title":"Consistent linear speedups to a first solution in parallel state-space search","author":"Saletore","year":"1990"},{"key":"10.1016\/0004-3702(93)90002-S_BIB51","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(93)90002-S_BIB52","series-title":"Chess Skill in Man and Machine","first-page":"82","article-title":"CHESS 4.5\u2014The Northwestern University Chess Program","author":"Slate","year":"1977"},{"issue":"2\u20133","key":"10.1016\/0004-3702(93)90002-S_BIB53","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF00127839","article-title":"Group graphs and computational symmetry on massively parallel architecture","volume":"5","author":"Stiller","year":"1991","journal-title":"J. Supercomput."},{"key":"10.1016\/0004-3702(93)90002-S_BIB54","year":"1990"},{"issue":"5","key":"10.1016\/0004-3702(93)90002-S_BIB55","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1109\/TC.1984.1676453","article-title":"Manip\u2014a multicomputer architecture for solving combinatorial extremum-search problems","volume":"33","author":"Wah","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0004-3702(93)90002-S_BIB56","article-title":"On the optimality of randomized alpha-beta search","author":"Zhang","year":"1992"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:000437029390002S?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:000437029390002S?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T00:53:02Z","timestamp":1553647982000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/000437029390002S"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,4]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,4]]}},"alternative-id":["000437029390002S"],"URL":"https:\/\/doi.org\/10.1016\/0004-3702(93)90002-s","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[1993,4]]}}}