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}