Programming G.K. Manacher Techniques Editor Computing Connected Components on Parallel Computers

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. Key Words and Phrases: graph theory, parallel processing, algorithms, transitive closure, connected componen