An Efficient Parallel Biconnectivity Algorithm

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 (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² /p) time and O (n²) space using any number p n² / ² 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 (n) time using processors and O (n) space on an exclusive-read exclusive-write parallel RAM.