Computing connected components on parallel computers
DS Hirschberg, AK Chandra, DV Sarwate - Communications of the ACM, 1979 - dl.acm.org
DS Hirschberg, AK Chandra, DV Sarwate
Communications of the ACM, 1979•dl.acm.orgWe present a parallel algorithm which uses n 2 processors to find the connected
components of an undirected graph with n vertices in time O (log2 n). An O (log2 n) time
bound also can be achieved using only n⌈ n/⌈ log2 n⌉⌉ 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.
components of an undirected graph with n vertices in time O (log2 n). An O (log2 n) time
bound also can be achieved using only n⌈ n/⌈ log2 n⌉⌉ 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.
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.
ACM Digital Library