A Randomized Linear-Work EREW PRAM Algorithm to Find a Minimum Spanning Forest |
| |
| Authors: | Chung Keung Poon and Vijaya Ramachandran |
| |
| Affiliation: | (1) Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong. ckpoon@cs.cityu.edu.hk., HK;(2) Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA. vlr@cs.utexas.edu., US |
| |
| Abstract: | 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. |
| |
| Keywords: | , Parallel algorithms, Minimum spanning tree, EREW PRAM, Design of algorithms, Randomized algorithms, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
