On efficient parallel strong orientation

DOI10.1016/0020-0190(85)90025-0zbMath0603.68067OpenAlexW2058557216MaRDI QIDQ1082819

Uzi Vishkin

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

zbMATH Keywords

graph algorithmparallel algorithmPRAMstrongly connected componentparallel random access machinesbridgeless graphs

Mathematics Subject Classification ID

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