An Optimal Parallel Co-Connectivity Algorithm

In this paper we consider the problem of computingthe connected components of the complement of a given graph.We describe a simple sequential algorithm for this problem,which works on the input graph and not on its complement,and which for a graph on n vertices and m edgesruns in optimal O(n+m) time.Moreover, unlike previous linear co-connectivity algorithms,this algorithm admits efficient parallelization, leading toan optimal O(log n)-time and O((n+m)log n)-processoralgorithm on the EREW PRAM model of computation.It is worth noting that, for the related problemof computing the connected components of a graph, no optimaldeterministic parallel algorithm is currently available.The co-connectivity algorithms find applications ina number of problems.In fact, we also include a parallel recognition algorithmfor weakly triangulated graphs, which takes advantage ofthe parallel co-connectivity algorithm and achievesan O(log² n) time complexity usingO((n+m²) log n) processors on the EREW PRAM model of computation.