Computing Connected Components on Parallel Computers We present a parallel algorithm which uses n2 processors to find the connected components of an undirected graph with n vertices in time O(log2n). An O(log2n) time bound also can be achieved using only n$n/$log2n)) processors. The algorithm can be used to find the transitive closure of a symmetric Boolean matrix. We assume that the processors have access to a common memory. Simultaneous access to the same location is permitted for fetch instructions but not for store instructions. CACM August, 1979 Hirschberg, D. Chandra, A. Sarwate, D. Graph theory, parallel processing, algorithms, transitive closure, connected component 5.25 5.32 6.22 CA790802 DB January 4, 1980 12:18 PM 3075 4 3156 3156 4 3156 3156 4 3156 3156 4 3156 2289 5 3156 2973 5 3156 3075 5 3156 3156 5 3156 3156 5 3156 3156 5 3156