Design and implementation of parallel graph algorithms for minimum spanning tree, list ranking, and root finding on trees

On a distributed memory machine, the running time of a parallel algorithm which requires extensive communication is likely to be dominated by the time for communication. For this reason, when designing parallel algorithms for such a machine, one is interested in (1) minimizing the total number of messages sent and received during the algorithm, taking constant factors into account, and (2) ensuring an even distribution of messages among processors.; We design different parallel minimum spanning tree (MST) algorithms based on Boruvka's sequential algorithm and compare their performance on the CM-5. Motivated by the experimental results, we study list ranking and root finding on trees.; We define the external work of an algorithm to be the number of messages sent during the execution of the algorithm and show that {dollar}2(n - 1){dollar} is a lower bound on the external work of list ranking in our parallel model. We also present an asymptotic analysis of a randomized list ranking algorithm which shows that, with all but exponentially small probability, the external work of the algorithm (1) is close to 2n on an input list of sufficiently large n elements, achieving near optimal performance, and (2) has {dollar}delta{dollar}-good distribution among P processors, that is, for any {dollar}delta > 0{dollar}, the external work on any processor is at most {dollar}(1 + delta){dollar} times the average, as long as n is sufficiently larger than P. Adapting the list ranking algorithm, we design an efficient algorithm for root finding on trees. Its external work is close to 3n with all but exponentially small probability and is expected to have O(1)-good distribution.