Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
From MaRDI portal
Publication:758188
DOI10.1016/0890-5401(91)90019-XzbMath0724.68012OpenAlexW2039757598MaRDI QIDQ758188
Uzi Vishkin, Richard John Cole
Publication date: 1991
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(91)90019-x
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15)
Related Items
A faster parallel algorithm for \(k\)-connectivity, Smallest bipartite bridge-connectivity augmentation, A parallel algorithm for finding a triconnected component separator with an application, Planarity testing in parallel, An I/O Efficient Algorithm for Minimum Spanning Trees, Graph Connectivity in Log Steps Using Label Propagation, The bridge-connectivity augmentation problem with a partition constraint
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel strong orientation of an undirected graph
- An optimal parallel connectivity algorithm
- Finding Euler tours in parallel
- On efficient parallel strong orientation
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- An optimally efficient selection algorithm
- Faster optimal parallel prefix sums and list ranking
- Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
- An Efficient Parallel Biconnectivity Algorithm
- Deterministic coin tossing with applications to optimal parallel list ranking
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Computing connected components on parallel computers
- Fast, Efficient Parallel Algorithms for Some Graph Problems
- Efficient parallel algorithms for some graph problems
- An O(logn) parallel connectivity algorithm
- Optimal Parallel 5-Colouring of Planar Graphs
- The Parallel Evaluation of General Arithmetic Expressions
