ABSTRACT

We give the first linear-work parallel algorithm for finding a minimum spanning tree. It is a randomized algorithm, and requires O(2log log n) expected time. It is a modification of the sequential linear-time algorithm of lein and Tarjan.