### An efficient and fast parallel-connected component algorithmAn efficient and fast parallel-connected component algorithm

Access Restriction
Subscribed

 Author Han, Yujie ♦ Wagner, Robert A. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1990 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of $\textit{e}$ edges and $\textit{n}$ nodes, the time complexity of the algorithm is $&Ogr;(\textit{e/p}$ + $(\textit{n}$ log $\textit{n})/\textit{p}$ + $log2\textit{n})$ with $\textit{p}$ processors. The algorithm can be further refined to yield time complexity $&Ogr;(\textit{H}(\textit{e},$ $\textit{n},$ $\textit{p})/\textit{p}$ + $(\textit{n}$ log $\textit{n})/(\textit{p}$ $log(\textit{n}/\textit{p}))$ + $log2\textit{n}),$ where $\textit{H}(\textit{e,$ n, p) is very close to $&Ogr;(\textit{e}).$ These results show that linear speedup can be obtained for up to $\textit{p}$ ≤ $\textit{e}/log2\textit{n}$ processors when $\textit{e}$ ≥ $\textit{n}$ log $\textit{n}.$ Linear speedup can still be achieved with up to $\textit{p}$ ≤ $\textit{n}ε$ processors, 0 ≤ ε < 1, for graphs satisfying $\textit{e}$ ≥ $\textit{n}$ $log(*)\textit{n}.$ Our results can be further improved if a more efficient integer sorting algorithm is available. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1990-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 37 Issue Number 3 Page Count 17 Starting Page 626 Ending Page 642

#### Open content in new tab

Source: ACM Digital Library