A Linear-Work Parallel Algorithm for Finding Minimum Spanning Trees
Report ID:
TR-457-94
Authors:
Date:
April 1994
Pages:
14
Download Formats:
Abstract:
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.
