Parallel Algorithmic Techniques For Combinational Computation
David Eppstein, Zvi Galil · Annual Review of Computer Science · 1988
We have described a number of algorithmic tools that have been found useful in the construction of parallel algorithms; among these are prefix computation, ranking, Euler tours, ear decomposition, and matrix calculations. We have also described some of the applications of these tools, and listed many other applications. These algorithms seem likely to be useful not only in their own right, but also as examples of ways to break up other problems into parts suitable for parallel solution.
Cited by 100 works. doi:10.1146/annurev.cs.03.060188.001313
Authors
References
- The Design and Analysis of Computer Algorithms
- Depth-First Search and Linear Graph Algorithms
- Non-separable and planar graphs
- Principles of Compiler Design
- Parallel Prefix Computation
- The Parallel Evaluation of General Arithmetic Expressions
- Parallelism in random access machines
- Parallelism in Comparison Problems
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Data parallel algorithms