{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:25Z","timestamp":1725663265780},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540505174"},{"type":"electronic","value":"9783540460305"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50517-2_79","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:26:05Z","timestamp":1330201565000},"page":"161-174","source":"Crossref","is-referenced-by-count":22,"title":["Superlinear speedup in parallel state-space search"],"prefix":"10.1007","author":[{"given":"V. Nageshwara","family":"Rao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vipin","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"13_CR1","unstructured":"M. Imai, Y. Yoshida, and T. Fukumura. A parallel searching scheme for multiprocessor systems and its application to combinatorial problems. In IJCAI, pages 416\u2013418, 1979."},{"key":"13_CR2","unstructured":"Virendra K. Janakiram, Dharma P. Agrawal, and Ram Mehrotra. Randomized parallel algorithms for prolog programs and backtracking applications. In Proceedings of International conference on Parallel Processing, pages 278\u2013281, 1987."},{"volume-title":"Search in Artificial Intelligence","year":"1988","key":"13_CR3","unstructured":"Laveen Kanal and Vipin Kumar (editors). Search in Artificial Intelligence. Springer-Verlag, New York, 1988 (in press)."},{"key":"13_CR4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"R.E. Korf","year":"1985","unstructured":"R.E. Korf. Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence, 27:97\u2013109, 1985. Also a chapter in 'search and Artificial Intelligence', Vipin Kumar and Laveen Kanal Eds, Springer-Verlag,1987(to appear).","journal-title":"Artificial Intelligence"},{"key":"13_CR5","unstructured":"Richard Korf. Personal communication. In the Univ. of California at Los Angeles, 1988."},{"key":"13_CR6","unstructured":"W. Kornfeld. The use of parallelism to implement a heuristic search. In IJCAI, pages 575\u2013580, 1981."},{"key":"13_CR7","first-page":"1004","volume-title":"Encyclopaedia of Artificial Intelligence: Vol 2","author":"V. Kumar","year":"1987","unstructured":"Vipin Kumar. Depth-first search. In Stuart C. Shapiro, editor, Encyclopaedia of Artificial Intelligence: Vol 2, pages 1004\u20131005, John Wiley and Sons, Inc., New York, 1987."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Vipin Kumar and Laveen N. Kanal. Parallel branch-and-bound formulations for and\/or tree search. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6, November 84.","DOI":"10.1109\/TPAMI.1984.4767600"},{"key":"13_CR9","unstructured":"Vipin Kumar, K. Ramesh, and V. Nageshwara Rao. Parallel heuristic search of state-space graphs: a summary of results. In Proceedings of the 1988 National Conference on Artificial Intelligence, August 1988. Also AI Lab Tech. Report 88-70, University of Texas at Austin, March 88."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Vipin Kumar and V. Nageshwara Rao. Parallel depth-first search, part II: analysis. International Journal of Parallel Programming, 16 (6), 1987.","DOI":"10.1007\/BF01389001"},{"key":"13_CR11","unstructured":"Kouichi Kumon, Hideo Masuzawa, and Akihiro Itashaki. Kabu-wake: a new parallel inference method and its evaluation. In Digest of papers \u2014 IEEE Computer Society International Conference, pages 168\u2013172, 1986."},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"T. H. Lai and Sartaj Sahni. Anomalies in parallel branch and bound algorithms. Communications of the ACM, 594\u2013602, 1984.","DOI":"10.1145\/358080.358103"},{"key":"13_CR13","unstructured":"Guo-Jie Li and Benjamin W. Wah. Computational Efficiency of Parallel Approximate Branch-and-Bound Algorithms. Technical Report TR-84-6, Purdue University, School of Electrical Engineering, FEBRUARY 84."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Guo-Jie Li and Benjamin W. Wah. Coping with anomalies in parallel branch-and-bound algorithms. IEEE Trans on Computers, C-35, June 1986.","DOI":"10.1109\/TC.1986.5009434"},{"key":"13_CR15","unstructured":"R. Mehrotra and E. Gehringer. Superlinear speedup through randomized algorithms. In Proceedings of International conference on Parallel Processing, pages 291\u2013300, 1985."},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Joseph Mohan. Experience with two parallel programs solving the traveling salesman problem. In Proceedings of International conference on Parallel Processing, pages 191\u2013193, 1983.","DOI":"10.21236\/ADA123327"},{"key":"13_CR17","series-title":"Technical Report","volume-title":"Superlinear Speedup for Parallel Backtracking","author":"B. Monien","year":"1986","unstructured":"B. Monien, E. Spekenmeyer, and O. Vornberger. Superlinear Speedup for Parallel Backtracking. Technical Report 30, Univ. of Paderborn, FRG, 1986."},{"key":"13_CR18","unstructured":"V. Nageshwara Rao, V. Kumar, and K. Ramesh. A parallel implementation of iterative-deepening-a*. In AAAI, pages 878\u2013882, 1987. Also AI Lab TR 87-46, University of Texas at Austin, January 87."},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"V. Nageshwara Rao and Vipin Kumar. Parallel depth-first search, part I: implementation. International Journal of Parallel Programming, 16 (6), 1987.","DOI":"10.1007\/BF01389000"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"D.S. Nau, V. Kumar, and L. Kanal. General branch-and-bound and its relation to a* and ao*. Artificial Intelligence, 23, 1984.","DOI":"10.1016\/0004-3702(84)90004-3"},{"key":"13_CR21","unstructured":"Nils J. Nilsson. Principles of Artificial Intelligence. Tioga Press, 1980."},{"key":"13_CR22","volume-title":"Heuristics \u2014 Intelligent Search Strategies for Computer Problem Solving","author":"J. Pearl","year":"1984","unstructured":"Judea Pearl. Heuristics \u2014 Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading, MA, 1984."},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Michael J. Quinn and Narsingh Deo. An upper bound for the speedup of parallel branch-and-bound algorithms. BIT, 6,No 1, March 1986.","DOI":"10.1007\/BF01939360"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"H. Stone and P. Sipala. The average complexity of depth-first search with backtracking and cutoff. IBM Journal of Research and Development, May 1986.","DOI":"10.1147\/rd.303.0242"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Peter Tinker. Performance and pragmaticsof an OR-parallel logic programming system. International Journal of Parallel Programming, ?, 1988.","DOI":"10.1007\/BF01379323"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50517-2_79.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:20Z","timestamp":1605647900000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50517-2_79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540505174","9783540460305"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-50517-2_79","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}