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 + in) 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 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. (c) 2007 Elsevier B.V. All rights reserved.