Introduction John H. Reif Part I Fundamental Parallel Graph Algorithms 1. Prefix Sums and Their Applications Guy Blelloch 2. List Ranking and Parallel Tree Contraction Margaret Reid-Miller, Gary Miller, Francesmary Modugno 3. Introduction to Parallel Connectivity, List Ranking, and Euler Tour Techniques Sara Baase Part II Advanced Parallel Graph Algorithms 4. Advanced Parallel Prefix-sums, List Ranking and Connectivity Uzi Vishkin 5. Randomized Parallel Connectivity Hillel Gazit 6. Parallel Lowest Common Ancestor Computation Baruch Schieber 7. Parallel Open Ear Decomposition with Applications to Graph Biconnectivity and Triconnectivity Vijaya Ramachandran 8. Parallel Graph Matching Vijay Vazirani Part III Parallel Sorting and Computational Geometry 9. Parallel Algorithms for Chordal Graphs Philip Klein 10. Dynamic Parallel Evaluation of Computation DAGs Erich Kaltofen 11. Parallel Evaluation of Logic Queries Jeffrey Ullman Part IV Fundamental Parallel Algebraic Algorithms 12. Parallel Merge Sort Richard Cole 13. Deterministic Parallel Computational Geometry Mikhail Atallah and Michael Goodrich Part V Advanced Parallel Algebraic Algorithms 14. Random Sampling Techniques and Parallel Algorithms Design Sanguthevar Rajasekaran and Sandeep Sen 15. Parallel Solution of Sparse Linear and Path Systems Victor Pan Part VI Extensions of Parallel Tree Contraction to Algebraic and Logical Problems 16. Parallel Algorithms for Network Flow Problems Andrew Goldberg 17. Newton Iteration and Integer Design Stephen Tate Part VII Parallel Combinatorial Optimization 18. Parallel Linear Algebra Joachim von zur Gathen 19. Parallel Resultant Computation Doug Ierardi and Dexter Kozen Part VIII Inherent Limitations of Parallel Computations 20. Polynomial Completeness and Parallel Computation Raymond Greenlaw 21. The Complexity of Computation on the Parallel Random Access Machine Faith Fich Part IX Asynchronous Parallel Computation 22. Asynchronous PRAM Algorithms Phillip Gibbons
