# What algorithm on a PRAM computes the connected components of a graph with least time complexity?

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?

• Is randomization allowed? – Hsien-Chih Chang 張顯之 Apr 8 '11 at 1:25
• @Chang: Nope, sorry, I am interesting in an exact algorithm. Good future question though. – Jeff Kubina Apr 8 '11 at 1:53
• You could be exact and randomized. i.e las vegas – Suresh Venkat Apr 8 '11 at 3:34
• 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. – 5501 Apr 8 '11 at 10:07
• @5501: You have the answer, thanks. Did you want to move it to the Answer section? – Jeff Kubina Apr 9 '11 at 0:30

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.