Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
Yung Hyang Tsin, Francis Y. L. Chin · SIAM Journal on Computing · 1984
In this paper, we present efficient parallel algorithms for the following graph problems: finding the lowest common ancestors for vertex pairs of a directed tree; finding all fundamental cycles, a directed spanning forest, all bridges, all bridge-connected components, all separation vertices, all biconnected components, and testing the biconnectivity of an undirected graph. All these algorithms achieve the $O(\lg ^2 n)$ time bound, with the first two algorithms using $n\lceil n /\lg n\rceil $ processors and the remaining algorithms using $n\lceil n/\lg ^2 n \rceil $ processors. In all cases, our algorithms are better than the previously known algorithms and in most cases reduce the number of processors used by a factor of $n\lg n$. Moreover, our algorithms are optimal with respect to the time-processor product for dense graphs, with the exception of the first two algorithms. The machine model we use is the PRAM which is a SIMD model allowing simultaneous reads but not simultaneous writes to the same memory location.