On efficient parallel strong orientation
From MaRDI portal
Publication:1082819
DOI10.1016/0020-0190(85)90025-0zbMath0603.68067OpenAlexW2058557216MaRDI QIDQ1082819
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(85)90025-0
graph algorithmparallel algorithmPRAMstrongly connected componentparallel random access machinesbridgeless graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (14)
On the optimal strongly connected orientations of city street graphs. IV: Four east-west avenues or north-south streets ⋮ Finding level-ancestors in trees ⋮ Parallel ear decomposition search (EDS) and st-numbering in graphs ⋮ Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM ⋮ The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time ⋮ An efficient parallel algorithm for updating minimum spanning trees ⋮ The complexity of parallel search ⋮ Data-Oblivious Graph Algorithms in Outsourced External Memory ⋮ Computational complexity of threshold automata networks under different updating schemes ⋮ Efficient parallel algorithms for doubly convex-bipartite graphs ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ Parallel search algorithms for graphs and trees ⋮ Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms ⋮ Faster optimal parallel prefix sums and list ranking
Cites Work
- Parallel strong orientation of an undirected graph
- An optimal parallel connectivity algorithm
- Sorting in \(c \log n\) parallel steps
- Depth-first search is inherently sequential
- An Efficient Parallel Biconnectivity Algorithm
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- An O(logn) parallel connectivity algorithm
- Finding Dominators in Directed Graphs
This page was built for publication: On efficient parallel strong orientation