Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

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]
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.