<p>As Jeff suggested, I moved my comment to the answer section: </p>

<p>On the CRCW PRAM, achieving  $O(\log n)$ time is fairly easy (see J. v. Leeuwen, Handbook of TCS, Chapter 17). </p>

<p>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. </p>

CC BY-SA 3.0
2011-04-09T09:52:17.913Z
2011-04-09T09:52:17.913Z
5501
<p>As suggested by @Suresh, the following paper provides exact results even though is randomized.</p>

<p>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 <a href="http://doi.acm.org/10.1145/181014.181017" rel="nofollow">http://doi.acm.org/10.1145/181014.181017</a></p>

<p>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. </p>

CC BY-SA 3.0
2011-04-08T19:29:05.090Z
2011-04-08T19:29:05.090Z
Massimo Cafaro
<p>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 <em>Finding connected components in O(log n loglog n) time on the EREW PRAM</em>, by K. Chong and T. Lam. Is there an algorithm with a smaller time complexity?</p>

CC BY-SA 3.0
2011-04-08T01:25:46.383Z
Is randomization allowed?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-04-08T01:53:21.683Z
@Chang: Nope, sorry, I am interesting in an exact algorithm. Good future question though.
Jeff Kubina
CC BY-SA 3.0
2011-04-08T03:34:27.890Z
You could be exact and randomized. i.e las vegas
Suresh Venkat
CC BY-SA 3.0
2011-04-08T10:07:11.413Z
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
CC BY-SA 3.0
2011-04-09T00:30:03.303Z
@5501: You have the answer, thanks. Did you want to move it to the Answer section?
Jeff Kubina
<ds.algorithms><reference-request><graph-algorithms><dc.parallel-comp>
What algorithm on a PRAM computes the connected components of a graph with least time complexity?
Jeff Kubina
# What algorithm on a PRAM computes the connected components of a graph with least time complexity?

(Asked by: username_0 on 2011-04-08)

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?

**Tags:** ds.algorithms, reference-request, graph-algorithms, dc.parallel-comp
> **Comments:**
> **username_1**: Is randomization allowed?  
> **username_0**: @Chang: Nope, sorry, I am interesting in an exact algorithm. Good future question though.  
> **username_2**: You could be exact and randomized. i.e las vegas  
> **username_3**: 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.  
> **username_0**: @5501: You have the answer, thanks. Did you want to move it to the Answer section?  

---

## 2 answers

### Answer by username_3 on 2011-04-09. Score: 6 | Accepted answer

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.


---

### Answer by username_4 on 2011-04-08. Score: 2

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.


---

