Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-457-94

Authors:

Date:

April 1994

Pages:

14

Download Formats:

We give the first linear-work parallel algorithm for finding a minimum

spanning tree. It is a randomized algorithm, and requires O(2^{log^*

n} log n) expected time. It is a modification of the sequential

linear-time algorithm of Klein and Tarjan.