Subodh Kumar Steve M. Goddard Jan F. Prins
Department of Computer Science
University of North Carolina
Chapel Hill NC 27599-3175, USA
We present efficient parallel algorithms for finding the connected components of sparse and dense graphs using a mesh-connected parallel computer. We start with a PRAM algorithm with work complexity $O(n^2\log n)$. The algorithm performs $O(\log n)$ reduction and broadcast operations on within the rows and columns of a mesh connected computer. Next, a representation of the adjacency matrix for a sparse graph with $m$ edges is chosen that preserves the communication structure of the algorithm but improves the work bound to $O((n+m) log n)$. This work bound can be improved to the optimal $O(n+m)$ bound through the use of graph contraction.
In architectures like the MasPar MP-1 and MP-2, parallel row and column operations of the form described achieve high performance relative to unrestricted concurrent accesses typically found in parallel connected component algorithms for sparse graphs and exhibit no locality dependence. We present MasPar MP-1 performance figures for implementations of the algorithms described. The implementations are exercised on a variety of parametrically-generated graphs, differing in structure and connectivity. These graphs are generated externally and read in as input for the algorithms, permitting comparison of different implementations on identical graphs. Opportunities for additional performance improvement of the implementations are described.