Connected components algorithms for mesh-connected parallel computers
Stephen M. Goddard, S. Kumar, Jan F. Prins · DIMACS series in discrete mathematics and theoretical computer science · 1997
We present a new CREW PRAM algorithm for finding connected components. For a graph G with n vertices and m edges, algorithmA 0 requires at most O(logn) parallel steps and performs O((n+m) log n)work in the worst case. The advantage our algorithm has over others in the literature is that it can be adapted to a 2-D mesh-connected communication model in whichall CREW operations are replaced by O(log n) parallel row and column operations without increasing the time complexity. We present the mapping of A 0 to a mesh-connected computer and describe two implementations, A 1 and A 2 . Algorithm A 1 , which uses an adjacency matrix to represent the graph, performs O(n² log n)work. Hence, it only achieves work efficiency on dense graphs. The second implementation, A 2 ,uses a sparse representation of the adjacency matrix and again performs O(logn) row and column operations but reduces the work to O((m + n)logn) on all graphs. We report MasPar MP-1 performance figures for imp...