| Article ID: | iaor20117032 |
| Volume: | 35 |
| Issue: | 3 |
| Start Page Number: | 257 |
| End Page Number: | 268 |
| Publication Date: | Mar 2003 |
| Journal: | Algorithmica |
| Authors: | Keung Poon Chung, Ramachandran Vijaya |
| Keywords: | datamining |
We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n ‐vertex graph the algorithm runs in o((log n)1+ϵ) expected time for any ϵ >0 and performs linear expected work. This is the first linear‐work, polylog‐time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general‐purpose models of parallel computation–the QSM and the BSP.