|
TR-457-94
A Linear-Work Parallel Algorithm for Finding Minimum Spanning Trees |
|
| Authors: | Cole, Richard, Klein, Philip N., Tarjan, Robert E. |
| Date: | May 1994 |
| Pages: | 14 pages |
| Download Formats: | [Postscript] |
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. |
|