Summary: 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)\) 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(\log^{2}n)\) time using \(O((n + m)/\log^{2}n)\) processors. The strong co-connectivity algorithm can also be parallelized to yield an \(O(\log^{2}n)\)-time and \(O(m^{1.188}/\log n)\)-processor solution. As a byproduct, we obtain a simple optimal \(O(\log n)\)-time parallel co-connectivity algorithm.
Our results show that, in a parallel process environment, the problems of computing the bi-connected 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.