| Call Number | SEM-212 |
| Collection Type | Indeks Artikel prosiding/Sem |
| Title | An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (Extended Abstract) |
| Author | Shay Halperin, Uri Zwick; |
| Publisher | 6th Annual ACM Symposium on Parallel Algorithms and Architecture |
| Subject | |
| Location |
| Nomor Panggil | ID Koleksi | Status |
|---|---|---|
| SEM-212 | TERSEDIA |
Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the connected compo- nents 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 com- plete in O(log n) time is at most n for any desired c > 0. The best deterministic EREW PRAM connectivity algo- rithm, obtained by Chong and Lam, runs in O(log n log log n) time using m + n processors.