An Efficient Parallel Biconnectivity Algorithm
Robert Endre Tarjan, Uzi Vishkin · SIAM Journal on Computing · 1985
In this paper we propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in $O(n + m)$ time and space on a graph of n vertices and m edges. A parallel implementation runs in $O(\log n)$ time and $O(n + m)$ space using $O(n + m)$ processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in $O(n^2 /p)$ time and $O(n^2 )$ space using any number $p \leqq n^2 /\log ^2 n$ of processors, on a concurrent-read, exclusive-write parallel RAM. The last algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique that simplifies and improves computation of various functions on trees is introduced. This technique typically requires $O(\log n)$ time using processors and $O(n)$ space on an exclusive-read exclusive-write parallel RAM.
Cited by 525 works. doi:10.1137/0214061
Authors
References
- GRAPH THEORY
- Depth-First Search and Linear Graph Algorithms
- GRAPHS AND HYPERGRAPHS
- An O(logn) parallel connectivity algorithm
- Computing connected components on parallel computers
- Finding Dominators in Directed Graphs
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Finding the maximum, merging, and sorting in a parallel computation model
- Finding the maximum, merging and sorting in a parallel computation model
- On the Parallel Evaluation of Certain Arithmetic Expressions