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-436-93
A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees
Authors: Klein, Philip N., Tarjan, Robert E.
Date:October 1993
Pages:9
Download Formats: [Postscript]
Abstract:
We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.