Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
DOI10.1016/0890-5401(91)90019-XzbMATH Open0724.68012OpenAlexW2039757598MaRDI QIDQ758188FDOQ758188
Authors: Uzi Vishkin, Richard 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
Recommendations
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- An efficient and fast parallel-connected component algorithm
- Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
- An optimal parallel connectivity algorithm
- Optimal parallel algorithms on planar graphs
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- An optimal parallel connectivity algorithm
- An Efficient Parallel Biconnectivity Algorithm
- Faster optimal parallel prefix sums and list ranking
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- The Parallel Evaluation of General Arithmetic Expressions
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- An O(logn) parallel connectivity algorithm
- On efficient parallel strong orientation
- Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
- 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
- Title not available (Why is that?)
- Computing connected components on parallel computers
- Fast, Efficient Parallel Algorithms for Some Graph Problems
- Efficient parallel algorithms for some graph problems
- Optimal Parallel 5-Colouring of Planar Graphs
- An optimally efficient selection algorithm
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- Parallel strong orientation of an undirected graph
- Finding Euler tours in parallel
Cited In (15)
- Smallest bipartite bridge-connectivity augmentation
- An I/O efficient algorithm for minimum spanning trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- A faster parallel algorithm for \(k\)-connectivity
- The bridge-connectivity augmentation problem with a partition constraint
- An optimal parallel connectivity algorithm
- Graph connectivity in log steps using label propagation
- A parallel algorithm for finding a triconnected component separator with an application
- Planarity testing in parallel
- Efficient parallel graph algorithms for coarse grained multicomputers and BSP
- Expected parallel time and sequential space complexity of graph and digraph problems
- Title not available (Why is that?)
- Fast Deterministic Processor Allocation
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
This page was built for publication: Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q758188)
