motivated in part by practical considerations. Among the many areas treated in the recent literature are sorting [2, 3, 7, 12, 15] , the evaluation of arithmetic expressions, linear recurrences and polynomials [4, 8, 10] , matrix algorithms [5, 6, 13] , and graph theory [9, 14, 15] . In this paper we present a parallel algorithm CONNECT which determines the connected components of an undirected graph with n vertices in time O(log2n) using n 2 processors. Next, we modify the algorithm to demonstrate an observation due to F.P. Preparata and R.L. Probert, viz., n[n/lg n] processors 1 suffice to achieve a time bound of O(log2n). Finally, we show that CONNECT can be modified to compute the transitive closure of an nxn symmetric Boolean matrix in time O(log2n) using n[n/lg n] processors. We use the single instruction stream-multiple data stream (SIMD) model of parallel processors. It is assumed that the processors have access to a common memory, and that simultaneous access to the same location is permitted for fetch instructions but not for store instructions. We present a parallel algorithm which uses n 2 processors to find the connected components of an undirected graph with n vertices in time O(log2n). An O0og2n) time bound also can be achieved using only n[n/[log2n]] processors. The algorithm can he 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.
Parallel Algorithms : Hirschberg, Chandra and Sarwate REF presented an O(log 2 n) time parallel algorithm using n 2 /logn processors on a CREW PRAM to find connected components of an undirected graph.
Computing connected components on parallel computers
CACM
Computer Science