1988/06/01 by David Eppstein, Zvi Galil · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Algorithms and Data Compression #Computation #Computer science #Parallel computing #Decomposition #Theoretical computer science #Prefix #Ranking (information retrieval) #Algorithm #Parallel algorithm #Matrix (chemical analysis) #Euler's formula #Mathematics #Artificial intelligence
paper · doi:10.1146/annurev.cs.03.060188.001313
openalex publication_date 1988/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/27
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.