BABYL OPTIONS: -*- rmail -*- Version: 5 Labels: Note: This is the header of an rmail file. Note: If you are seeing it in rmail, Note: it means the file has no messages in it.  1, deleted, filed,, Summary-line: 7-Dec bhatt@bellcore.com #some biblo entries Received: from flash.bellcore.com (flash.bellcore.com [192.4.13.90]) by mailee.bellcore.com (8.6.4/8.6.4) with SMTP id KAA29537 for ; Tue, 7 Dec 1993 10:52:49 -0500 Received: from random.bellcore.com (random.bellcore.com [192.4.4.52]) by flash.bellcore.com (8.6.4/8.6.4) with SMTP id KAA23903 for ; Tue, 7 Dec 1993 10:52:39 -0500 Received: from localhost (bhatt@localhost) by random.bellcore.com (8.6.4/8.6.4) id KAA19179; Tue, 7 Dec 1993 10:52:35 -0500 Date: Tue, 7 Dec 1993 10:52:35 -0500 From: bhatt@bellcore.com (Sandeep Bhatt) Message-Id: <199312071552.KAA19179@random.bellcore.com> To: pangfeng@bellcore.com In-reply-to: Pang Feng's message of Mon, 6 Dec 1993 16:22:02 -0500 <199312062122.QAA01038@babo.bellcore.com> Subject: some biblo entries *** EOOH *** @STRING{header = " ----------------------------------------------------------------------------- File: minimax.bib Version: V01-005 of April 2nd, 1993 Author: Claude G. Diderich 30, Avenue S.Reymondin, CH-1009 Pully, Switzerland, Europe E-mail: diderich@dma.epfl.ch Copyright: (c) 1992..93 by Claude G. Diderich, Switzerland Non commercial usage permitted as long as the above copyright no- tice is included. Note: Please send all modifications and additions to this file to diderich@dma.epfl.ch.AVAILABLE indicates if a copy of the article is available to me (If you have a copy of an article marked NO, I would be gratefull if you could send me a copy of it).Any other indication in the AVAILABLE field are for personal use of the author. Thanks: I would like to thank the following persons (in alphabetical or- MONTH der) for their contributions: David Barnard , Bruno Charlier Van-Dat Cung , Rainer Feldmann , Marc Gengler , Rattikorn Hewett , Toshihide Ibaraki , L. V. Kale , Richard E. Korf , Bradley C. Kuszmauk , T. A. Marsland , Judea Pearl , Wim Pijls , Udo Sprute ----------------------------------------------------------------------------- "} @STRING{artint = "Artificial Intelligence"} @STRING{ieeetoc = "{IEEE} Transactions on Computers"} @STRING{ieeetopami = "{IEEE} Transactions on Pattern Analysis and Machine Intelligence"} @STRING{ijprai = "International Journal of Pattern Recognition and Artificial Intelligence"} @STRING{iccaj = "ICCA Journal"} @STRING{jalgo = "Journal of Algorithms"} @STRING{jpdc = "Journal of Parallel and Distributed Computing"} @STRING{parcomp = "Parallel Computing"} @STRING{infocon = "Information and Control"} @STRING{spex = "Software: Practice and Experience"} @INPROCEEDINGS{Abra88, AUTHOR = "Bruce Abramson and Richard E. Korf", TITLE = "A Model of Two-player Evaluation Functions", BOOKTITLE = "Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI-87)", ADDRESS = "Seattle, WA", YEAR = 1987, MONTH = Jul, PAGES = "90--94", AVAILABLE = "ETHICS" } @ARTICLE{Abra89, AUTHOR = "Bruce Abramson", TITLE = "Control Strategies for Two-Player Games", JOURNAL = acmcs, VOLUME = 21, NUMBER = 2, PAGES = "137--161", MONTH = Jun, YEAR = 1989 } @TECHREPORT{Akl79, AUTHOR = "Selim G. Akl and David T. Barnard and Ralph J. Doran", TITLE = "Searching Game Trees in Parallel", INSTITUTION = "Queen's University, Department of Computing and Information Science", YEAR = 1979, MONTH = Nov, NOTE = "\Star", AVAILABLE = "NO" } @INPROCEEDINGS{Akl80, AUTHOR = "Selim G. Akl and David T. Barnard and Ralph J. Doran", TITLE = "Simulation and Analysis in Deriving Time and Storage Requirements for a Parallel Alpha-beta Algorithm", BOOKTITLE = "International Conference on Parallel Processing", PAGES = "231--234", YEAR = 1980, AVAILABLE = "ETHICS" } @ARTICLE{Akl82, AUTHOR = "Akl, Selim G. and Barnard, David T. and Doran, Ralph J.", TITLE = "Design, Analysis, and Implementation of a Parallel Tree Search Algorithm", JOURNAL = ieeetopami, YEAR = 1982, VOLUME = "PAMI-4", NUMBER = 2, MONTH = Mar, PAGES = "192--203" } @INBOOK{Akl89, AUTHOR = "Selim G. Akl", TITLE = "The Design and Analysis of Parallel Algorithms", CHAPTER = "12 -- Traversing Combinatorial Spaces", PAGES = "310--340", PUBLISHER = "Prentice Hall", ADDRESS = "Englewood Cliffs, NJ", YEAR = 1989, AVAILABLE = "EPFL-BC" } @TECHREPORT{Almq88, AUTHOR = "Kenneth Almquist and Neil McKenzie and Kenneth Sloan", TITLE = "An Inquiry into Parallel Algorithms for Searching Game Trees", INSTITUTION = "University of Washington, Department of Computer Science", ADDRESS = "Seattle, WA", YEAR = 1988, MONTH = Dec, NUMBER = "88-12-03" } @TECHREPORT{Alth88, AUTHOR = {Ingo Alth\"ofer}, TITLE = "A Parallel Game Tree Search Algorithm with a Linear Speedup", YEAR = 1988, MONTH = Dec, NOTE = "submitted to Journal of Algorithms, accepted 1992", INSTITUTION = {University of Bielefeld, Faculty for Mathematics}, ADDRESS = "Bielefeld, Germany" } @ARTICLE{Alth90, AUTHOR = {Ingo Alth\"ofer}, TITLE = "An Incremental Negamax Algorithm", JOURNAL = artint, YEAR = 1990, VOLUME = 43, PAGES = "57--65" } @ARTICLE{Alth91, AUTHOR = {Ingo Alth\"ofer and Bernhard Balkenhol}, TITLE = "A Game Tree with Distinct Leaf Values which is easy for the Alpha-beta Algorithm", JOURNAL = artint, PAGES = "183--190", VOLUME = 52, YEAR = 1991, AVAILABLE = "EPFL-DMA" } @PHDTHESIS{Amig91, AUTHOR = "Claude Amiguet", TITLE = "Contr\^oleurs Distribu\'es pour la Programmation Heuristique", SCHOOL = "Swiss Federal Institute of Technology, Department of Computer Science", NUMBER = 910, ADDRESS = "Lausanne, Switzerland", YEAR = 1991, NOTE = "In french" } @INPROCEEDINGS{Bal86a, AUTHOR = "Henri E. Bal and Robbert {van Renesse}", TITLE = "Parallel Alpha-Beta Search", BOOKTITLE = "Proceedings NGI-SION Symposium Stimulerende Informatica", ADDRESS = "Utrecht, Netherlands", PAGES = "379--385", MONTH = Apr, YEAR = 1986, AVAILABLE = "EPFL-LITH" } @ARTICLE{Ball86b, AUTHOR = "Henri E. Bal and Robbert {van Renesse}", TITLE = "A Summary of Parallel Alpha-Beta Search Results", JOURNAL = iccaj, YEAR = 1986, VOLUME = 9, NUMBER = 3, PAGES = "146--149", MONTH = Sep, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Ball83, AUTHOR = "Bruce W. Ballard", TITLE = "The *-Minimax Search Procedure for Trees Containing Chance Nodes", JOURNAL = artint, VOLUME = 21, PAGES = "327--350", YEAR = 1983 } @ARTICLE{Baud78a, AUTHOR = "G\'erard M. Baudet", TITLE = "On the Branching Factor of the Alpha-Beta Pruning Algorithm", JOURNAL = artint, VOLUME = 10, PAGES = "173--199", YEAR = 1978 } @PHDTHESIS{Baud78b, AUTHOR = "G\'erard M. Baudet", TITLE = "The Design and Analysis of Algorithms for Asynchronous Multiprocessors", SCHOOL = "Carnegie Mellon University", YEAR = 1978, NUMBER = "CMU-CS-78-116", ADDRESS = "Pittsburgh, PA", AVAILABLE = "ETHICS MICROFICHES" } @INBOOK{Beal80, AUTHOR = "D. F. Beal", CHAPTER = "An Analysis of Minimax", TITLE = "Advances in Computer Chess 2", YEAR = 1980, NOTE = "Editor: M. R. B. Clarke", PAGES = "103--109", PUBLISHER = "Edinburgh University Press.", AVAILABLE = "ETHICS" } @PHDTHESIS{Berl75, AUTHOR = "Hans Jack Berliner", TITLE = "Chess as Problem Solving", SCHOOL = "Carnegie Mellon University", YEAR = 1975, ADDRESS = "Pittsburgh, PA", AVAILABLE = "ETHICS MICROFICHES" } @ARTICLE{Berl89, AUTHOR = "Hans Jack Berliner and Carl Eberling", TITLE = "Pattern Knowledge and Search: {T}he {SUPREME} Architecture", JOURNAL = artint, YEAR = 1989, VOLUME = 38, NUMBER = 2, PAGES = "161--198" } @ARTICLE{Berl90, AUTHOR = "Hans Jack Berliner and Gordon Goetsch and Murray S. Campbell and Carl Ebeling", TITLE = "Measuring the Performance Potential of Chess Programs", JOURNAL = artint, YEAR = 1990, VOLUME = 43, NUMBER = 1, MONTH = Apr, PAGES = "7--21", AVAILABLE = "EPFL-DMA" } @TECHREPORT{Bohm89, AUTHOR = {Max B\"ohm and Ewald Speckenmeyer}, TITLE = "A Dynamic Processor Tree for Solving Game Trees in Parallel", INSTITUTION = "University of Dortmund, Fachbereich Informatik", ADDRESS = "Dortmund, Germany", YEAR = 1989, AVAILABLE = "Also in: Proceedings SOR '89" } @TECHREPORT{Bord90, AUTHOR = "Andrei Z. Broder and Anna R. Karlin and Prabhakar Raghavan and Eli Upfal", TITLE = "On the Parallel Complexity of Evaluating Game-Trees", INSTITUTION = "IBM Research Division", NUMBER = "RR RJ 7729", MONTH = Oct, YEAR = 1990, NOTE = "\Star", AVAILABLE = "NO" } @INBOOK{Brat82, AUTHOR = "I. Bratko and M. Gams", CHAPTER = "Error Analysis of the Minimax Principle", TITLE = "Advances in Computer Chess 3", YEAR = 1982, NOTE = "Editor: M. R. B. Clarke", PAGES = "1--15", PUBLISHER = "Pergamon Press", AVAILABLE = "ETHICS" } @ARTICLE{Camp83, AUTHOR = "Murray S. Campbell and T. A. Marsland", TITLE = "A Comparison of Minimax Tree Search Algorithms", JOURNAL = artint, VOLUME = 20, PAGES = "347--367", YEAR = 1983 } @ARTICLE{Chak92, AUTHOR = "P. P. Chakrabarti and S. Ghose", TITLE = "A General Best First Search Algorithm in And/Or Graphs", JOURNAL = jalgo, VOLUME = 13, NUMBER = 2, PAGES = "177-187", MONTH = Jun, YEAR = 1992, AVAILABLE = "EPFL-DMA" } @TECHREPORT{Cung91, AUTHOR = "Van-Dat Cung and Catherine Roucairol", TITLE = "Parallel Minimax Tree Searching", INSTITUTION = "INRIA", TYPE = "RR", NUMBER = 1549, YEAR = 1991, MONTH = Nov, NOTE = "In French, will appear in English" } @ARTICLE{Darw83, AUTHOR = "Nevin M. Darwish", TITLE = "A Quantitative Analysis of the Alpha-Beta Pruning Algorithm", JOURNAL = artint, VOLUME = 21, PAGES = "405--433", YEAR = 1983 } @TECHREPORT{Dide92, AUTHOR = "Claude G. Diderich", TITLE = "Evaluation des Performances de l'Algorithme {SSS*} avec Phases de Synchronisation sur une Machine Parall\`ele \`a M\'emoires Distribu\'ees", ADDRESS = "Lausanne, Switzerland", INSTITUTION = "Swiss Federal Institute of Technology, Department of Computer Science, Laboratory for Theoretical Computer Science", MONTH = Jun, YEAR = 1992, NOTE = "In french", AVAILABLE = "Contact for a copy" } @MASTERSTHESIS{Feld87, AUTHOR = "Rainer Feldmann and Peter Mysliwietz", TITLE = "{Parallele Spielbaumsuche}", NOTE = "Diplomarbeit, In german", SCHOOL = "University of Paderborn", ADDRESS = "Paderborn, Germany", YEAR = 1987, MONTH = Dec } @ARTICLE{Feld89, AUTHOR = "Rainer Feldmann and Burkhard Monien and Peter Mysliwietz and Oliver Vornberger", TITLE = "Distributed Game Tree Search", JOURNAL = iccaj, VOLUME = 12, NUMBER = 2, YEAR = 1989, PAGES = "65--73", NOTE = "\Star", AVAILABLE = "NO" } @INPROCEEDINGS{Feld90a, AUTHOR = "Rainer Feldmann and Burkhard Monien and Peter Mysliwietz and Oliver Vornberger", TITLE = "Distributed Game Tree Search", BOOKTITLE = "Parallel Algorithms for Machine Intelligence and Vision", EDITOR = "Vipin Kumar, P. S. Gopalakrishnan, Laveen N. Kanal", PUBLISHER = "Springer-Verlag", PAGES = "66--101", YEAR = 1990, AVAILABLE = "EPFL-BC" } @INBOOK{Feld90b, AUTHOR = "Rainer Feldmann and Peter Mysliwietz and Burkhard Monien", TITLE = "Advances in Computer Chess 6", CHAPTER = "1 --- A Fully Distributed Chess Program", PAGES = "1--27", PUBLISHER = "Ellis Horwood", YEAR = 1990, AVAILABLE = "ETHICS", NOTE = "Editor: D. Beal", } @INPROCEEDINGS{Feld90c, AUTHOR = "Rainer Feldmann, Peter Mysliwietz, Burkhard Monien", TITLE = "{Spielbaumsuche auf einem Transputernetzwerk}", BOOKTITLE = "Parallel - Algorithmen und -Rechnerstrukturen (PARS), Workshop Sprachen und Systeme zur Parallelverarbeitung", PUBLISHER = {Gesellschaft f\"ur Informatik}, YEAR = 1990, MONTH = Jan, NOTE = "In german" } @INPROCEEDINGS{Feld91a, AUTHOR = "Rainer Feldmann and Peter Mysliwietz and Burkhard Monien", TITLE = "Distributed Game Tree Search on a Massively Parallel System", BOOKTITLE = "Data structures and efficient algorithms: Final report on the {DFG} special joint initiative", PUBLISHER = "Springer-Verlag", EDITOR = "B. Monien, Th. Ottmann", PAGES = "270--288", VOLUME = "LNCS 594", MONTH = Sep, YEAR = 1991, AVAILABLE = "EPFL-BC" } @INPROCEEDINGS{Feld91b, AUTHOR = "Rainer Feldmann and Peter Mysliwietz and Burkhard Monien", TITLE = "Experiments with a Fully Distributed Chess Program", BOOKTITLE = "Heuristic Programming in Artificial Intelligence 3", EDITOR = "J. van den Herik, V. Allis", YEAR = 1991, PAGES = "72--87", NOTE = "Also in: Tech.Report, University Paderborn, Paderborn, Germany" } @INPROCEEDINGS{Felt88, AUTHOR = "E. W. Felten and S. W. Otto", TITLE = "Chess on a Hypercube", BOOKTITLE = "The Third Conference on Hypercube Concurrent Computers and Applications", EDITOR = "Geoffrey Fox", PAGES = "1329--1341", VOLUME = "II-Applications", YEAR = 1988, ADDRESS = "Passadena, CA", AVAILABLE = "ETHICS" } @INPROCEEDINGS{Ferg88, AUTHOR = "C. Ferguson and Richard E. Korf", TITLE = "Distributed Tree Search and its application to alpha-beta pruning", BOOKTITLE = "Proceedings of the Seventh National Conference Artificial Intelligence (AAAI-88)", ADDRESS = "Minneapolis, MN", YEAR = 1988, MONTH = Aug, PAGES = "128--132", AVAILABLE = "ETHICS" } @INPROCEEDINGS{Fink80, AUTHOR = "Raphael A. Finkel and John P. Fishburn", TITLE = "Parallel Alpha-Beta Search on Arachne", BOOKTITLE = "IEEE International Conference on Parallel Processing", PAGES = "235--243", YEAR = 1980, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Fink82, AUTHOR = "Raphael A. Finkel and John P. Fishburn", TITLE = "Parallelism in Alpha-Beta Search", JOURNAL = artint, YEAR = 1982, VOLUME = 19, PAGES = "89--106" } @ARTICLE{Fink83, AUTHOR = "Raphael A. Finkel and John P. Fishburn", TITLE = "Improved Speedup Bounds for Parallel Alpha-Beta Search", JOURNAL = ieeetopami, YEAR = 1983, VOLUME = "PAMI-5", NUMBER = 1, PAGES = "89--92" } @INBOOK{Fish84, AUTHOR = "John P. Fishburn", TITLE = "Analysis of Speedup in Distributed Algorithms", CHAPTER = "4 -- {P}arallel Alpha-Beta Search", PAGES = "11-54", PUBLISHER = "UMI Research Press", YEAR = 1984, VOLUME = 14, SERIES = "Computer Science: Distributed Database Systems", NOTE = "Revision of thesis (PhD) -- University of Wisconsin, Madison, 1981" } @TECHREPORT{Full73, AUTHOR = "S. H. Fuller and J. G. Gaschnig and J. J. Gillogly", TITLE = "An Analysis of the Alpha-beta Pruning Algorithm", ADDRESS = "Pittsburgh", INSTITUTION = "Carnegie-Mellon University, Department of Computer Science", MONTH = Jul, YEAR = 1973, NOTE = "\Star", AVAILABLE = "NO" } @INPROCEEDINGS{Hewe92, AUTHOR = "R. Hewett and K. Ganesan", TITLE = "Consistent Linear Speedup in Parallel Alpha-Beta Search", BOOKTITLE = "ICCI'92, Computing and Information", PUBLISHER = "IEEE Computer Society Press", PAGES = "237--240", YEAR = 1992, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Hiro87, AUTHOR = "Usui Hiromoto and Yamashita Masafumi and Imai Masaharu and Ibaraki, Toshihide", TITLE = "Parallel Searches of Game Trees", JOURNAL = "Systems and Computers in Japan", NUMBER = "8", PAGES = "97--109", VOLUME = 18, YEAR = 1987, AVAILABLE = "ETHICS" } @ARTICLE{Hora90, AUTHOR = "Helmut Horacek", TITLE = "Reasonning with Uncertainty in Computer Chess", JOURNAL = artint, YEAR = 1990, VOLUME = 43, PAGES = "37--56" } @INBOOK{Hsu89, AUTHOR = "Feng-Hsiung Hsu and T. S. Anantharaman and Murray S. Campbell and A. Nowatzyk", TITLE = "Computers, Chess, and Cognition", CHAPTER = "5 Deep Thought", PAGES = "55--78", YEAR = 1990, PUBLISHER = "Springer Verlag", AVAILABLE = "ETHICS" } @PHDTHESIS{Hsu90, AUTHOR = "Feng-Hsiung Hsu", TITLE = "Large Scale Parallelization of Alpha-Beta Search: An Algorithmic and Architectural Study with Computer Chess", SCHOOL = "Carnegie Mellon University", MONTH = Feb, YEAR = 1990, NUMBER = "CMU-CS-90-108", ADDRESS = "Pittsburgh, PA" } @ARTICLE{Hunt88, AUTHOR = "Matthew M. Huntbach and F. Warren Burton", TITLE = "Alpha-Beta Search on Virtual Tree Machines", JOURNAL = "Information Sciences", PAGES = "3--17", VOLUME = 44, YEAR = 1988, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Hyat89, AUTHOR = "R. M. Hyatt and B. W. Suter", TITLE = "A Parallel Alpha/Beta Tree Searching Algorithm", JOURNAL = "Parallel Computing", PAGES = "299--308", VOLUME = 10, YEAR = 1989, AVAILABLE = "EPFL-BC" } @ARTICLE{Ibar86, AUTHOR = "Toshihide Ibaraki", TITLE = "Generalization of Alpha-Beta and {SSS*} Search Procedures", JOURNAL = artint, YEAR = 1986, VOLUME = 29, PAGES = "73--117" } @INPROCEEDINGS{Ibar87, AUTHOR = "Toshihide Ibaraki", TITLE = "Game Solving Procedure {H*} is Unsurpassed", BOOKTITLE = "Discrete Algorithms and Complexity", EDITOR = "D. S. Johnson and al.", PAGES = "185--200", YEAR = 1987, PUBLISHER = "Academic Press, Inc.", AVAILABLE = "ETHICS" } @INPROCEEDINGS{Ibar91a, AUTHOR = "Toshihide Ibaraki", TITLE = "Search Algorithms for Minimax Game Trees", BOOKTITLE = "Comference: Twenty Years NP-Completeness", ADDRESS = "Sicily, Italy", MONTH = Jun, YEAR = 1991, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Ibar91b, AUTHOR = "Toshihide Ibaraki and Yoshiroh Katoh", TITLE = "Searching Minimax Game Trees Under Memory Space Constraint", JOURNAL = "Annals of Mathematics and Artificial Intelligence", PAGES = "141--153", VOLUME = 1, YEAR = 1990, AVAILABLE = "ETHICS" } @ARTICLE{Kain91, AUTHOR = "Kaindl, Hermann and Shams, Reza and Horacek, Helmut", TITLE = "Minimax Search Algorithms with and without Aspiration Windows", JOURNAL = ieeetopami, YEAR = 1991, VOLUME = "PAMI-13", NUMBER = 12, MONTH = Dec, PAGES = "1225--1235" } @INPROCEEDINGS{Karp89, AUTHOR = "Richard M. Karp and Yanjun Zhang", TITLE = "On parallel evaluation of game trees", BOOKTITLE = "First ACM Annual symposium on parallel algorithms and architectures (SPAA'89)", PUBLISHER = "ACM", ADDRESS = "New York, NY", PAGES = "409--420", YEAR = 1989, AVAILABLE = "ETHICS" } @ARTICLE{Kato88, AUTHOR = "Y. Katoh and Toshihide Ibaraki", TITLE = "Game Solving Procedure {SSS*} is Unsurpassed", JOURNAL = "Systems and computers in Japan", YEAR = 1988, VOLUME = 19, NUMBER = 7, PAGES = "93-103", AVAILABLE = "ETHICS" } @MASTERSTHESIS{Klei90, AUTHOR = "Theo Klein Paste and Patrick {van der Laag}", TITLE = "An Analysis of the {SSS*} Algorithm", SCHOOL = "Erasmus University Rotterdam", ADDRESS = "Rotterdam, NL", YEAR = 1990, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Knut75, AUTHOR = "Donald E. Knuth and Ronald W. Moore", TITLE = "An Analysis of Alpha-Beta Pruning", JOURNAL = artint, VOLUME = 6, NUMBER = 4, PAGES = "293--326", YEAR = 1975 } @ARTICLE{Korf85, AUTHOR = "Richard E. Korf", TITLE = "Iterative Deepening: {An} Optimal Admissible Tree Search", JOURNAL = artint, VOLUME = 27, YEAR = 1985, PAGES = "97--109", AVAILABLE = "EPFL-DMA" } @INPROCEEDINGS{Korf89, AUTHOR = "Richard E. Korf", TITLE = "Generalized Game Trees", BOOKTITLE = "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-89)", ADDRESS = "Detroit, MI", YEAR = 1989, MONTH = Aug, PAGES = "328--333", AVAILABLE = "ETHICS" } @ARTICLE{Korf90, AUTHOR = "Richard E. Korf", TITLE = "Depth-Limited Search for Real-Time Problem Solving", JOURNAL = "The Journal of Real-Time Systems", PAGES = "7--24", YEAR = 1990, AVAILABLE = "EPFL-LITH" } @ARTICLE{Korf91, AUTHOR = "Richard E. Korf", TITLE = "Multi-Player alpha-beta pruning", JOURNAL = artint, MONTH = Feb, NUMBER = 1, YEAR = 1991, VOLUME = 48, PAGES = "99--111", AVAILABLE = "EPFL-DMA" } @PHDTHESIS{Kraa90, AUTHOR = "H.-J. Kraas", TITLE = "Zur {Parallelisierung} des {SSS*-Algorithmus}", SCHOOL = "University of Braunschweig", ADDRESS = "Braunschweig, Germany", YEAR = 1990, NOTE = "In german, \Star", AVAILABLE = "NO" } @ARTICLE{Kuma83, AUTHOR = "Vipin Kumar and Laveen N. Kanal", TITLE = "A General Branch and Bound Formulation for Understanding and Synthesizing And/Or Tree Search Procedures", JOURNAL = artint, PAGES = "179--198", VOLUME = 21, YEAR = 1983, AVAILABLE = "EPFL-DMA" } @ARTICLE{Kuma84, AUTHOR = "Vipin Kumar and Laveen N. Kanal", TITLE = "Parallel Branch-and-Bound Formulations for {AND/OR} Tree Search", JOURNAL = ieeetopami, MONTH = Nov, NUMBER = 6, PAGES = "768--778", VOLUME = "PAMI-6", YEAR = 1984, AVAILABLE = "EPFL-BC" } @INPROCEEDINGS{Kuma88, AUTHOR = "Vipin Kumar and Laveen N. Kanal", TITLE = "A General Branch and Bound Formulation for And/Or Graph and Game Tree Search", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer Verlag", YEAR = 1988, AVAILABLE = "ETHICS" } @INPROCEEDINGS{Leif85, AUTHOR = "Daniel B. Leifker and Laveen N. Kanal", TITLE = "A Hybrid {SSS*}/Alpha-Beta Algorithm for Parallel Search of Game Trees", BOOKTITLE = "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-85)", PAGES = "1044--1046", YEAR = 1985, AVAILABLE = "ETHICS" } @ARTICLE{Leve92, AUTHOR = "Willem G. Levelt and M. Frans Kaashoek and Henri E. Bal and Andrew S. Tanenbaum", TITLE = "A Comparison of Two Paradigms for Distributed Shared Memory", JOURNAL = spex, VOLUME = 22, NUMBER = 11, MONTH = Nov, YEAR = 1992, PAGES = "985--1010" } @ARTICLE{Li90, AUTHOR = "Liwu Li and T. A. Marsland", TITLE = "Probability-Based Game Tree Pruning", JOURNAL = jalgo, YEAR = 1990, MONTH = Mar, NUMBER = 1, VOLUME = 11, PAGES = "27--43", AVAILABLE = "EPFL-DMA" } @TECHREPORT{Lind83, AUTHOR = "Gary Lindstrom", TITLE = "The Key Node Method: A Highly-Parallel Alpha-Beta Algorithm", ADDRESS = "Salt Lake City", INSTITUTION = "University of Utah, Department of Computer Science", MONTH = Mar, NUMBER = "UUCS 83-101", YEAR = 1983, NOTE = "\Star", AVAILABLE = "NO" } @MASTERSTHESIS{Low91, AUTHOR = "Chin-Chau Low", TITLE = "Parallel Game Tree Searching with Lower and Upper Bounds", SCHOOL = "University of Illinois at Urbana Campaign", ADDRESS = "IL", YEAR = 1991, ADVISOR = "L.V.Kale" } @ARTICLE{Mars82, AUTHOR = "T. A. Marsland and Murray S. Campbell", TITLE = "Parallel Search of Strongly Ordered Game Trees", JOURNAL = acmcs, VOLUME = 14, NUMBER = 4, PAGES = "533--551", MONTH = Dec, YEAR = 1982 } @INPROCEEDINGS{Mars83a, AUTHOR = "T. A. Marsland", TITLE = "Relative Efficiency of Alpha-Beta Implementations", BOOKTITLE = "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-83)", YEAR = 1983, PAGES = "763--766", ADDRESS = "Karlsruhe, Germany", MONTH = Aug, NOTE = "\Star", AVAILABLE = "NO" } @TECHREPORT{Mars83b, AUTHOR = "T. A. Marsland and Fred Popowich", TITLE = "Multiprocessor Tree Searching System Design", INSTITUTION = "University of Alberta, Department of Computer Science", YEAR = 1983, NUMBER = "TR 83-06", ADDRESS = "Edmonton, Canada", MONTH = Jul } @ARTICLE{Mars85, AUTHOR = "T. A. Marsland and Fred Popowich", TITLE = "Parallel Game-Tree Search", JOURNAL = ieeetopami, YEAR = 1985, VOLUME = "PAMI-7", NUMBER = 4, MONTH = Jul, PAGES = "442--452" } @ARTICLE{Mars87, AUTHOR = "Marsland, T. A. and Reinefeld, Alexander and Schaeffer, Jonathan", TITLE = "Low Overhead Alternatives to {SSS*}", JOURNAL = artint, VOLUME = 31, PAGES = "185--199", YEAR = 1987 } @INBOOK{Mars88, AUTHOR = "T.A. Marsland and M. Olafsson and Jonathan Schaeffer", TITLE = "Multiprocessor Tree-Search Experiments", BOOKTITLE = "Advances in Computer Chess IV", NOTE = "D.F. Beal (Editor)", PUBLISHER = "Pergamon Press", PAGES = "37--51", YEAR = 1986, AVAILABLE = "NO" } @ARTICLE{McAl88, AUTHOR = "David Allen McAllester", TITLE = "Conspiracy Numbers for Min-Max Searching", JOURNAL = artint, VOLUME = 35, PAGES = "287--310", YEAR = 1988 } @ARTICLE{Meul90, AUTHOR = "M. van der Meulen", TITLE = "Conspiracy Number Search", JOURNAL = iccaj, VOLUME = 13, NUMBER = 1, YEAR = 1990, MONTH = Mar, PAGES = "3--14", NOTE = "\Star", AVAILABLE = "NO" } @PHDTHESIS{Mich83, AUTHOR = "Gerard P. Michon", TITLE = "Recursive Random Games: {A} Probabilistic Model for Perfect Information Games", SCHOOL = "University of California at Los Angeles, Computer Science Department", ADDRESS = "Los Angeles, CA", NUMBER = "840029 (R-32)", YEAR = 1983 } @INPROCEEDINGS{Moni87, AUTHOR = "Burkhard Monien and Oliver Vornberger", TITLE = "Parallel Processing of Combinatorial Search Trees", BOOKTITLE = " Proceedings International Workshop on Parallel Algorithms and Architectures, Math. Research Nr. 38, Akademie - Verlag Berlin", PAGES = "60--69", YEAR = 1987, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Nau82, AUTHOR = "Danna S. Nau", TITLE = "The Last Player Theorem", JOURNAL = artint, VOLUME = 18, PAGES = "53--65", YEAR = 1982 } @ARTICLE{Nau83, AUTHOR = "Danna S. Nau", TITLE = "Pathology on Game Trees Revisited, and an Alternative to Minimaxing", JOURNAL = artint, VOLUME = 21, PAGES = "221--244", YEAR = 1983 } @ARTICLE{Newb77, AUTHOR = "Monroe M. Newborn", TITLE = "The Efficiency of the Alpha-Beta Search on Trees with Branch-dependent Terminal Node Scores", JOURNAL = artint, VOLUME = 8, PAGES = "137--153", YEAR = 1977 } @ARTICLE{Newb88, AUTHOR = "Monroe M. Newborn", TITLE = "Unsynchronized Iteratively Deepening Parallel Alpha-Beta Search", JOURNAL = ieeetopami, YEAR = 1988, VOLUME = "PAMI-10", NUMBER = 5, PAGES = "687--694" } @BOOK{Nils80, AUTHOR = "Nils J. Nilsson", TITLE = "Principles of Artificial Intelligence", PUBLISHER = "Tioga Publishing Company", ADDRESS = "Palo Alto, CA", YEAR = 1980, AVAILABLE = "ETHICS" } @ARTICLE{Pear80, AUTHOR = "Judea Pearl", TITLE = "Asymptotical Properties of Minimax Trees and Game Searching Procedures", JOURNAL = artint, VOLUME = 14, NUMBER = 2, PAGES = "113--138", YEAR = 1980 } @ARTICLE{Pear82, AUTHOR = "Judea Pearl", TITLE = "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality", JOURNAL = cacm, MONTH = Aug, YEAR = 1982, VOLUME = 25, NUMBER = 8, PAGES = "559--564" } @ARTICLE{Pear83, AUTHOR = "Judea Pearl", TITLE = "On the Nature of Pathology in Game Searching", JOURNAL = artint, VOLUME = 20, YEAR = 1983, PAGES = "427--453", AVAILABLE = "EPFL-DMA" } @BOOK{Pear84, AUTHOR = "Judea Pearl", TITLE = "Heuristics -- Intelligent Search Strategies for Computer Problem Solving", PUBLISHER = "Addison-Wesley Publishing Co.", ADDRESS = "Reading, MA", YEAR = 1984 } @PHDTHESIS{Pijl91, AUTHOR = "Wim Pijls", TITLE = "Shortest Paths and Game Trees", SCHOOL = "Erasmus University Rotterdam", YEAR = 1991, MONTH = Nov, ADDRESS = "Rotterdam, NL" } @TECHREPORT{Pijl92a, AUTHOR = "Wim Pijls and Arie Bruin", TITLE = "Another View of the {SSS*} Algorithm", INSTITUTION = "Erasmus University Rotterdam", YEAR = 1992, MONTH = Jan, ADDRESS = "Rotterdam, NL", NOTE = "Also in: Algorithms, Proceedings of the International Symposium, SIGAL'90, Tokyo, Japan, Aug. 1990" } @TECHREPORT{Pijl92b, AUTHOR = "Wim Pijls and Arie Bruin", TITLE = "Searching Informed Game Trees", INSTITUTION = "Erasmus University Rotterdam", YEAR = 1992, ADDRESS = "Rotterdam, NL", NOTE = "Extended abstract. Also in: Proceedings CSN '92 (Computer Science in the Netherlands), Mathematical Center, Amsterdam, 1992" } @TECHREPORT{Pijl92c, AUTHOR = "Wim Pijls and Arie Bruin", TITLE = "Searching Informed Game Trees", INSTITUTION = "Erasmus University Rotterdam", YEAR = 1992, MONTH = Oct, ADDRESS = "Rotterdam, NL", NUMBER = "EUR-CS-92-02" } @INBOOK{Powl90, AUTHOR = "Powley, C. and C. Ferguson and Richard E. Korf", TITLE = "Parallel heuristic search: Two approaches", BOOKTITLE = "Parallel Algorithms for Machine Intelligence and Vision", YEAR = 1990, PAGES = "42--65", PUBLISHER = "Springer-Verlag", AVAILABLE = "EPFL", NOTE = "Edited by V. Kumar, P. S. Gopalakrishnan and L.N." } @TECHREPORT{Popo83, AUTHOR = "Fred Popowich and T. A. Marsland", TITLE = "Parabelle: Experiences With a Parallel Chess Program", YEAR = 1983, MONTH = Aug, INSTITUTION = "University of Alberta, Department of Computer Science", ADDRESS = "Edmonton, Canada", NUMBER = "TR 83-07", NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Powl91, AUTHOR = "C. Powley and Richard E. Korf", TITLE = "Single Agent Parallel Window Search", JOURNAL = ieeetopami, YEAR = 1991, VOLUME = "PAMI-13", NUMBER = 5, MONTH = May, PAGES = "466--477" } @ARTICLE{Prak88, AUTHOR = "Bettadapu Prakash and T. A. Marsland", TITLE = "Accuracy and Savings in Depth-Limited Capture Search", JOURNAL = "International Journal of Man-Machine Studies", YEAR = 1988, VOLUME = 29, NUMBER = 6, PAGES = "497--502", AVAILABLE = "ETHICS" } @INPROCEEDINGS{Rein85, AUTHOR = "Alexander Reinefeld and Jonathan Schaeffer and T. A. Marsland", TITLE = "Information Acquisition in Minimal Window Search", BOOKTITLE = "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-85)", PAGES = "1040--1043", VOLUME = 2, YEAR = 1985, AVAILABLE = "ETHICS" } @BOOK{Rein89, AUTHOR = "Alexander Reinefeld", TITLE = "Spielbaum Suchverfahren", PUBLISHER = "Springer Verlag", VOLUME = "Informatik-Fachberichte 200", YEAR = 1989, AVAILABLE = "NO" } @TECHREPORT{Reza92, AUTHOR = "Jaleh Rezaie and Raphael Finkel", TITLE = "A Comparison of some Parallel Game-Tree Search Algorithms", INSTITUTION = "University of Kentucky, Department of Computer Science", ADDRESS = "Lexington, USA", YEAR = 1992 } @ARTICLE{Rive87, AUTHOR = "Ronald L. Rivest", TITLE = "Game Tree Searching by Min/Max Approximation", JOURNAL = artint, YEAR = 1987, VOLUME = 34, NUMBER = 1, PAGES = "77--96" } @TECHREPORT{Roiz81, AUTHOR = "Igor Roizen", TITLE = "On the Average Number of Terminal Nodes Examined by Alpha-Beta", INSTITUTION = "University of California at Los Angeles, Cognitive Systems Laboratory", YEAR = 1981, NUMBER = "UCLA-ENG-CSL-8108", ADDRESS = "Los Angeles, CA", NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Roiz83, AUTHOR = "Igor Roizen and Judea Pearl", TITLE = "A Minimax Algorithm Better than Alpha-Beta? Yes and No", JOURNAL = artint, VOLUME = 21, PAGES = "199--230", YEAR = 1983 } @ARTICLE{Scha83, AUTHOR = "Jonathan Schaeffer", TITLE = "The History Heuristic", JOURNAL = iccaj, VOLUME = 6, NUMBER = 3, PAGES = "16--19", YEAR = 1983, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Scha89a, AUTHOR = "Jonathan Schaeffer", TITLE = "Distributed Game-Tree Searching", JOURNAL = jpdc, VOLUME = 6, PAGES = "90--114", YEAR = 1989 } @ARTICLE{Scha89b, AUTHOR = "Jonathan Schaeffer", TITLE = "The History Heuristic and Alpha-Beta Search Enhancements in Practice", JOURNAL = ieeetopami, YEAR = 1989, VOLUME = "PAMI-11", NUMBER = 1, MONTH = Nov, PAGES = "1203--1212" } @ARTICLE{Scha90, AUTHOR = "Jonathan Schaeffer", TITLE = "Conspiracy Numbers", JOURNAL = artint, YEAR = 1990, VOLUME = 43, PAGES = "67--84" } @INBOOK{Schr86, AUTHOR = {G. Schr\"ufer}, CHAPTER = "Presence and Absence of Pathology on Game Trees", TITLE = "Advances in Computer Chess 4", YEAR = 1986, NOTE = "Editor: D. F. Beal", PAGES = "101--112", PUBLISHER = "Pergamon Press", AVAILABLE = "ETHICS" } @PHDTHESIS{Schr88, AUTHOR = {G. Schr\"ufer}, TITLE = {{Minimax-Suchen Kosten, Qualit\"at und Algorithmen}}, SCHOOL = "University of Braunschweig", ADDRESS = "Braunschweig, West Germany", YEAR = 1988, NOTE = "In german, \Star", AVAILABLE = "NO" } @ARTICLE{Shan50, AUTHOR = "Claude E. Shannon", TITLE = "Programming a Computer for Playing Chess", JOURNAL = "Philosophical Magazine", VOLUME = 41, PAGES = "256--275", YEAR = 1950, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Shen85, AUTHOR = "Chien-Chung Shen and Wen-Hsiang Tsai", TITLE = "A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion", JOURNAL = ieeetoc, VOLUME = "C-34", MONTH = Mar, YEAR = 1985, PAGES = "197--203", AVAILABLE = "EPFL-LITH" } @ARTICLE{Shin91, AUTHOR = "Rajjan Shinghal and Sofia Shved", TITLE = "Proposed Modifications to Parallel State Space Search of Game Trees", JOURNAL = ijprai, NUMBER = 5, VOLUME = "5", PAGES = "809--833", YEAR = 1991, AVAILABLE = "ETHICS" } @ARTICLE{Slag69, AUTHOR = "James H. Slagle and John K. Dixon", TITLE = "Experiments With SOme Programs That Search Game Trees", JOURNAL = jacm, VOLUME = 16, NUMBER = 2, YEAR = 1969, MONTH = Apr, PAGES = "189--207" } @INPROCEEDINGS{Stei90, AUTHOR = "Igor Steinberg and Marvin Solomon", TITLE = "Searching Game Trees in Parallel", BOOKTITLE = "International Conference on Parallel Processing", PAGES = "III-9 -- III-17", YEAR = 1990, NOTE = "\Star", AVAILABLE = "NO" } @ARTICLE{Stoc79, AUTHOR = "G. C. Stockman", TITLE = "A Minimax Algorithm Better than alpha-beta?", JOURNAL = artint, VOLUME = 12, NUMBER = 2, PAGES = "179--196", YEAR = 1979 } @ARTICLE{Tars83, AUTHOR = "M. Tarsi", TITLE = "Optimal Search on Some Game Trees", JOURNAL = jacm, YEAR = 1983, VOLUME = 30, PAGES = "389--396", MONTH = Jul, NOTE = "Also as Tech. Report UCLA-ENG-CSL-8108" } @INPROCEEDINGS{Vorn87, AUTHOR = "Oliver Vornberger and Burkhard Monien", TITLE = "Parallel Alpha-Beta versus Parallel {SSS*}", BOOKTITLE = "IFIP Conference on Distributed Processing", ADDRESS = "Amsterdam, NL", PUBLISHER = "North-Holland", PAGES = "613--625", MONTH = Oct, YEAR = 1987, AVAILABLE = "ETHICS" } \bibitem{AbrahamsonDKP87} K.~Abrahamson, N.~Dadoun, D.~A. Kirkpatrick, and T.~Pryztycka. \newblock A simple parallel tree contraction algorithm. \newblock Technical Report 87--30, Department of Computer Science, University of British Columbia, Vancouver, B. C., Canada, 1987. \bibitem{AggarwalA88} A.~Aggarwal and R.~J. Anderson. \newblock A random {{\cal NC}} algorithm for depth first search. \newblock {\em Combinatorica}, 8(1):1--12, 1988. \bibitem{AggarwalAK89} A.~Aggarwal, R.~J. Anderson, and M.-Y. Kao. \newblock Parallel depth-first search in general directed graphs. \newblock In {\em Proceedings of the 21st Annual {ACM} Symposium on Theory of Computing}, pages 297--308, May 1989. \bibitem{AhoHU74} A.~V. Aho, J.~E. Hopcroft, and J.~D. Ullman. \newblock {\em The Design and Analysis of Computer Algorithms}. \newblock Addison--Wesley, Reading, MA, 1974. \bibitem{Akl89} S.~G. Akl. \newblock {\em The Design and Analysis of Parallel Algorithms}. \newblock Prentice--Hall, Englewood Cliffs, NJ, 1988. \bibitem{AndersonM88} R.~J. Anderson and G.~L. Miller. \newblock Deterministic parallel list ranking. \newblock In J.~Reif, editor, {\em \booknuminseries{319}{Aegean Workshop on Computing: {VLSI} Algorithms and Architectures}{Lecture Notes in Computer Science}}, pages 81--90, New York, NY, June 1988. Springer--Verlag. \bibitem{AtallahV84} M.~Atallah and U.~Vishkin. \newblock Finding {Euler} tours in parallel. \newblock {\em Journal of Computer and System Sciences}, 29(3):330--337, July 1984. \bibitem{AwerbuchIS84} B.~Awerbuch, A.~Israeli, and Y.~Shiloach. \newblock Finding {Euler} circuits in logarithmic parallel time. \newblock In {\em Proceedings of the 16th Annual {ACM} Symposium on Theory of Computing}, pages 249--257, April 1984. \bibitem{AwerbuchS83} B.~Awerbuch and Y.~Shiloach. \newblock New connectivity and {MSF} algorithms for {U}ltracomputer and {PRAM}. \newblock In {\em Proceedings of the 1983 International Conference on Parallel Processing}, pages 175--179. {IEEE} Computer Society Press, August 1983. \bibitem{BorodinH85} A.~Borodin and J.~E. Hopcroft. \newblock Routing, merging, and sorting on parallel models of computation. \newblock {\em Journal of Computer and System Sciences}, 30(1):130--145, February 1985. \bibitem{Brent74} R.~P. Brent. \newblock The parallel evaluation of general arithmetic expressions. \newblock {\em Journal of the {ACM}}, 21(2):201--208, April 1974. \bibitem{Cole88} R.~Cole. \newblock Parallel merge sort. \newblock {\em {SIAM} Journal on Computing}, 17(4):770--785, August 1988. \bibitem{ColeV86b} R.~Cole and U.~Vishkin. \newblock Approximate and exact parallel scheduling with applications to list, tree, and graph problems. \newblock In {\em Proceedings of the 27th Annual Symposium on Foundations of Computer Science}, pages 478--491. {IEEE} Computer Society Press, October 1986. \bibitem{ColeV86a} R.~Cole and U.~Vishkin. \newblock Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. \newblock In {\em Proceedings of the 18th Annual {ACM} Symposium on Theory of Computing}, pages 206--219, May 1986. \bibitem{EppsteinG88} D.~Eppstein and Z.~Galil. \newblock Parallel algorithmic techniques for combinatorial computation. \newblock Unpublished manuscript. \bibitem{FortuneW78} S.~Fortune and J.~Wyllie. \newblock Parallelism in random access machines. \newblock In {\em Proceedings of the 10th Annual {ACM} Symposium on Theory of Computing}, pages 114--118, 1978. \bibitem{GalilP88} Z.~Galil and V.~Pan. \newblock Improved processor bounds for combinatorial problems in {RNC}. \newblock {\em Combinatorica}, 8(2):189--200, 1988. \bibitem{GibbonsR88} A.~Gibbons and W.~Rytter. \newblock {\em Efficient Parallel Algorithms}. \newblock Cambridge University Press, Cambridge, England, 1988. \bibitem{GoldbergPS87} A.~V. Goldberg, S.~A. Plotkin, and G.~E. Shannon. \newblock Parallel symmetry-breaking in sparse graphs. \newblock In {\em Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing}, pages 315--324, May 1987. \bibitem{Goldshlager78} L.~M. Goldshlager. \newblock A unified approach to models of synchronous parallel machines. \newblock In {\em Proceedings of the 10th Annual {ACM} Symposium on Theory of Computing}, pages 89--94, 1978. \bibitem{HirshbergCS79} D.~S. Hirshberg, A.~K. Chandra, and D.~V. Sarwate. \newblock Computing connected components on parallel computers. \newblock {\em Communications of the {ACM}}, 22(8):461--464, August 1979. \bibitem{Karloff86} H.~Karloff. \newblock A {Las} {Vegas} {RNC} algorithm for maximum matching. \newblock {\em Combinatorica}, 6(4):387--391, 1986. \bibitem{KarpR90} R.~M. Karp and V.~Ramachandran. \newblock Parallel algorithms for shared-memory machines. \newblock In J.~van Leeuwen, editor, {\em Handbook of Theoretical Computer Science}, pages 869--941. Elsevier Science Publishers, B. V., Amsterdam, The Netherlands, 1990. \bibitem{KarpUW86} R.~M. Karp, E.~Upfal, and A.~Wigderson. \newblock Constructing a perfect matching is in random {$NC$}. \newblock {\em Combinatorica}, 6(1):35--48, 1986. \bibitem{KosarajuD88} S.~R. Kosaraju and A.~L. Delcher. \newblock Optimal parallel evaluation of tree-structured computations by raking. \newblock In J.~Reif, editor, {\em \booknuminseries{319}{Aegean Workshop on Computing: {VLSI} Algorithms and Architectures}{Lecture Notes in Computer Science}}, pages 101--110. Springer--Verlag, New York, NY, June 1988. \bibitem{Kruskal83} C.~P. Kruskal. \newblock Searching, merging, and sorting in parallel computation. \newblock {\em {IEEE} Transactions on Computers}, C--32(10):942--946, October 1983. \bibitem{MillerRK88} G.~Miller, V.~Ramachandran, and E.~Kaltofen. \newblock Efficient parallel evaluation of straight-line code and arithmetic circuits. \newblock {\em {SIAM} Journal on Computing}, 17(4):687--695, August 1988. \bibitem{MillerR85} G.~Miller and J.~Reif. \newblock Parallel tree contraction and its application. \newblock In {\em Proceedings of the 26th Annual Symposium on Foundations of Computer Science}, pages 478--489. {IEEE} Computer Society Press, October 1985. \bibitem{MillerT87} G.~Miller and {S.-H.} Teng. \newblock Dynamic parallel complexity of computational circuits. \newblock In {\em Proceedings of the 19th Annual {ACM} Symposium on Theory of Computing}, pages 254--263, May 1987. \bibitem{MulmuleyVV87} K.~Mulmuley, U.~V. Vazirani, and V.~V. Vazirani. \newblock Matching is as easy as matrix inversion. \newblock {\em Combinatorica}, 7:105--113, 1987. \bibitem{SavitchS79} W.~J. Savitch and M.~Stimson. \newblock Time bounded random access machines with parallel processing. \newblock {\em Journal of the {ACM}}, pages 103--118, 1979. \bibitem{ShiloachV81} Y.~Shiloach and U.~Vishkin. \newblock Finding the maximum, merging, and sorting in a parallel computation model. \newblock {\em Journal of Algorithms}, 2:88--102, 1981. \bibitem{ShiloachV82} Y.~Shiloach and U.~Vishkin. \newblock An {$O(\log n)$} parallel connectivity algorithm. \newblock {\em Journal of Algorithms}, 3:57--67, 1982. \bibitem{Strassen73} V.~Strassen. \newblock Vermeidung von divisionen. \newblock {\em Crelles J. Reine Angew. Math.}, 264:182--202, 1973. \bibitem{Tarjan83} R.~E. Tarjan. \newblock {\em Data Structures and Network Algorithms}. \newblock {SIAM}, Philadelphia, PA, 1983. \bibitem{TarjanV84} R.~E. Tarjan and U.~Vishkin. \newblock Finding biconnected components and computing tree functions in logarithmic parallel time. \newblock In {\em Proceedings of the 25th Annual Symposium on Foundations of Computer Science}, pages 12--20. {IEEE} Computer Society Press, October 1984. \bibitem{ValiantS81} L.~Valiant and S.~Skyum. \newblock Fast parallel computation of polynomials using few processors. \newblock In {\em \booknuminseries{118}{Mathematical Foundations of Computer Science 1981}{Lecture Notes in Computer Science}}, pages 263--277. Springer--Verlag, New York, NY, 1981. \bibitem{ValiantSBR83} L.~Valiant, S.~Skyum, S.~Berkowitz, and C.~Rackoff. \newblock Fast parallel computation of polynomials using few processors. \newblock {\em {SIAM} Journal on Computing}, 12(4):641--644, November 1983. \bibitem{Valiant75} L.~G. Valiant. \newblock Parallelism in comparison problems. \newblock {\em {SIAM} Journal on Computing}, 4(3):348--355, 1975. \bibitem{Wein91} J.~Wein. \newblock Las vegas {RNC} algorithms for unary weighted matching and {T}-join problems. \newblock {\em Information Processing Letters}, 1991. \newblock To appear. \bibitem{Wyllie79} J.~C. Wyllie. \newblock {\em The Complexity of Parallel Computations}. \newblock PhD thesis, Cornell University, Ithaca, NY, August 1979. \end{thebibliography}