A Linear-Work Parallel Algorithm for Finding Minimum Spanning Trees
Report ID: TR-457-94Author: Tarjan, Robert E. / Cole, Richard / Klein, Philip N.
Date: 1994-05-00
Pages: 14
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.