On the parallel computation of the biconnected and strongly connected co-components of graphs

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m   edges both run in optimal O(n+m)O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search.Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in O(log2n) time using O((n+m)/log2n) processors. The strong co-connectivity algorithm can also be parallelized to yield an O(log2n)-time and O(m1.188/logn)O(m1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)O(logn)-time parallel co-connectivity algorithm.Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.