An efficient and fast parallel-connected component algorithm

Abstract

A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of e edges and n nodes, the time complexity of the algorithm is Ο( e/p + ( n log n )/ p + log ² n ) with p processors. The algorithm can be further refined to yield time complexity Ο( H ( e , n , p )/ p + ( n log n )/( p log( n / p )) + log ² n ), where H ( e, n, p ) is very close to Ο( e ). These results show that linear speedup can be obtained for up to p ≤ e /log ² n processors when e ≥ n log n . Linear speedup can still be achieved with up to p ≤ n ε processors, 0 ≤ ε < 1, for graphs satisfying e ≥ n log ^(*) n . Our results can be further improved if a more efficient integer sorting algorithm is available.