Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1979 | 10.1145/359138.359141 | Commun. ACM |
Keywords | Field | DocType |
parallel algorithm,n vertex,symmetric boolean matrix,simultaneous access,store instruction,parallel computer,transitive closure,computing connected component,parallel processing,time o,graph theory,connected component,algorithms,common memory,n2 processor | Graph theory,Graph,Combinatorics,Vertex (geometry),Logical matrix,Computer science,Parallel algorithm,Parallel processing,Theoretical computer science,Connected component,Transitive closure | Journal |
Volume | Issue | ISSN |
22 | 8 | 0001-0782 |
Citations | PageRank | References |
147 | 39.85 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| D. S. Hirschberg | 1 | 1265 | 506.25 |
| A. K. Chandra | 2 | 157 | 41.28 |
| D. V. Sarwate | 3 | 431 | 121.44 |