The fastest method to compute the connected components of an undirected graph on a PRAM I have found is O(log n loglog n) in the 1993 paper Finding connected components in O(log n loglog n) time on the EREW PRAM, by K. Chong and T. Lam. Is there an algorithm with a smaller time complexity?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Is randomization allowed? $\endgroup$– Hsien-Chih Chang 張顯之Apr 8, 2011 at 1:25
-
$\begingroup$ @Chang: Nope, sorry, I am interesting in an exact algorithm. Good future question though. $\endgroup$– Jeff KubinaApr 8, 2011 at 1:53
-
1$\begingroup$ You could be exact and randomized. i.e las vegas $\endgroup$– Suresh VenkatApr 8, 2011 at 3:34
-
4$\begingroup$ On the CRCW PRAM, achieving $O(\log n)$ time is fairly easy (see Handbook of TCS). On the EREW PRAM, Chong, Han and Lam (JACM 2001) give on $O(\log n)$ algorithm for MST on an EREW PRAM. Doesn't this also solve the CC problem? Alternatively, use Reingold's logspace algorithm for undirected connectivity and standard simulation methods. $\endgroup$– 5501Apr 8, 2011 at 10:07
-
1$\begingroup$ @5501: You have the answer, thanks. Did you want to move it to the Answer section? $\endgroup$– Jeff KubinaApr 9, 2011 at 0:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
As Jeff suggested, I moved my comment to the answer section:
On the CRCW PRAM, achieving $O(\log n)$ time is fairly easy (see J. v. Leeuwen, Handbook of TCS, Chapter 17).
On the EREW PRAM, Chong, Han and Lam (JACM, Vol 48(2), 2001) give an $O(\log n)$ algorithm for MST on an EREW PRAM. This should also solve the CC problem. Alternatively, use Reingold's logspace algorithm for undirected connectivity and standard simulation methods.
$\begingroup$
$\endgroup$
As suggested by @Suresh, the following paper provides exact results even though is randomized.
Shay Halperin and Uri Zwick. 1994. An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract). In Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures (SPAA '94). ACM, New York, NY, USA, 1-10. DOI=10.1145/181014.181017 http://doi.acm.org/10.1145/181014.181017
From the abstract: Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected components of a graph G=(V,E) with n vertices and m edges in O(log n) time using an optimal number of O((m+n)/log n) processors. The result returned by the algorithm is always correct. The probability that the algorithm will not complete in O(log n) time is at most 1/n^c for any desired c > 0.
