Thumbnail
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

   Open content in new tab
Source: ACM Digital Library