Computing connected components on parallel computers
D. S. Hirschberg, Ashok K. Chandra, D.V. Sarwate · Communications of the ACM · 1979
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 (log 2 n ). An O (log 2 n ) time bound also can be achieved using only n ⌈ n /⌈log 2 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.
Cited by 266 works. doi:10.1145/359138.359141 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Sorting networks and their applications
- The Parallel Evaluation of General Arithmetic Expressions
- Fast Parallel Matrix Inversion Algorithms
- Sorting on a mesh-connected parallel computer
- New Parallel-Sorting Schemes
- Cellular arrays for the solution of graph problems
- Optimal algorithms for parallel polynomial evaluation
- Fast parallel sorting algorithms
- Optimal Sorting Algorithms for Parallel Computers