# 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? Apr 8, 2011 at 1:25
• @Chang: Nope, sorry, I am interesting in an exact algorithm. Good future question though. Apr 8, 2011 at 1:53
• You could be exact and randomized. i.e las vegas Apr 8, 2011 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, 2011 at 10:07
• @5501: You have the answer, thanks. Did you want to move it to the Answer section? Apr 9, 2011 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.