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