Parallel algorithmic techniques for combinatorial computation

David Eppstein and Zvi Galil
Annual Reviews in Computer Science 3:233–283, 1988
Proc. 16th Int. Coll. Automata, Languages, and Programming (ICALP 1989), Lecture Notes in Computer Science 372, Giorgio Ausiello, Mariangiola Dezani-Ciancaglini, and Simona Ronchi Della Rocca, ed., Springer-Verlag, Jul 1989, pp. 304–318,
Tech. report CUCS-326-88, Columbia Univ., Computer Science Dept., 1988
Mathematical Reviews 91g:68042

Cited by:

• Parallel algorithms for dynamic programming recurrences with more than $O(1)$ dependency
• The APRAM: incorporating asynchrony into the PRAM model
• An Introduction to Parallel Algorithms
• A practical hierarchical model of parallel computation I: the model
• Optimal merging and sorting on the EREW PRAM
• Parallel retrieval of scattered information
• Every robust CRCW PRAM can efficiently simulate a priority PRAM
• Optimal parallel algorithms on planar graphs
• Planar depth-first search in $O(\log n)$ parallel time
• Fast parallel generation of random permutations
• Constant-time parallel integer sorting
• Improved deterministic parallel integer sorting
• Structural parallel algorithmics
• Finding all nearest neighbors for convex polygons in parallel — a new lower bound technique and a matching algorithm
• On parallel hashing and integer sorting
• Some triply-logarithmic parallel algorithms
• Parallel algorithms for shared-memory machines
• General purpose parallel architectures
• A bridging model for parallel computation
• Parametrization of Newton iteration for computations with structured matrices and applications
• Concurrent iterative algorithm for Toeplitz-like linear systems
• Parallel complexity of tridiagonal symmetric eigenvalue problem
• Improved parallel computations with matrices and polynomials
• Fast and efficient parallel solution of sparse linear systems
• A parallelization of Miller's $O(n^{\log n})$ isomorphism technique
• A parallel randomized approximation scheme for shortest paths
• Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values
• Space-efficient parallel merging
• Uniform circuits and exclusive read PRAMs
• Parallel algorithms for VLSI routing
• Efficient parallel algorithms can be made robust
• OAL: an implementation of an actor language on a massively parallel message-passing architecture
• Achieving optimal CRCW PRAM fault-tolerance
• Fast and efficient simulations among CRCW PRAMs
• Prefix graphs and their applications
• Fast parallel algorithms for all-sources lexicographic search and path-algebra problems
• Basic parallel algorithmic techniques for shared-memory machines
• Parallel dynamic programming
• Parallel string matching algorithms
• Efficient String Algorithmics
• Controlling memory access concurrency in efficient fault-tolerant parallel algorithms
• Efficient parallelism vs reliable distribution: a trade-off for concurrent computations
• Fault-Tolerant and Efficient Parallel Computation
• Pointers versus arithmetic in PRAMs
• Limits on the power of parallel random-access machines with weak forms of write conflict resolution
• The Complexity of Computation on the Parallel Random Access Machine
• Reliable computations on a faulty EREW PRAM
• A work-time optimal algorithm for computing all string covers
• Parallel algorithms with processor failures and delays
• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• Computer Algorithms
• Computer Algorithms/C++
• A randomized parallel algorithm for single-source shortest paths
• Fast randomized parallel methods for planar convex hull construction
• Approximate string searching
• Triply-logarithmic parallel upper and lower bounds for minimum and range minima over small domains
• Fast rectangular matrix multiplication and applications
• Parallel Algorithms
• Parallel Computation: Models & Methods
• On the power of some PRAM models
• There Are Parallel and Dynamic Shortest-Path Algorithms for Sparse Graphs
• Parallel computing: performance metrics and models
• General purpose parallel computing
• A case for the PRAM as a standard programmer's model
• Parallel complexity of computations with general and Toeplitz-like matrices Filled with integers and extensions
• Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
• Efficient parallel algorithms on restartable fail-stop processors
• Towards practical deteministic write-all algorithms
• In-place techniques for parallel convex hull algorithms
• Efficient parallel algorithms for manipulating sorted sets
• Failure-sensitive analysis of parallel algorithms with controlled memory access concurrency
• Additional patterns for parallel application programs
• Parallel Algorithms For Graph Problems