Quick links

Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

Report ID:
TR-289-90
Date:
June 1990
Pages:
13
Download Formats:
[PDF]

Abstract:

Komlos has devised a way to use a linear number of binary comparisons to test whether a given spanning tree of a graph with edge costs is a minimum spanning tree. The total computational work required by his method is much larger than linear, however. We describe a linear-time algorithm for verifying a minimum spanning tree. Our algorithm combines the result of Komlos with a preprocessing and table look-up method for small subproblems and with a previously known almost-linear-time algorithm. Additionally, we present an optimal deterministic algorithm and a linear-time randomized algorithm for sensitivity analysis of minimum spanning trees.

Follow us: Facebook Twitter Linkedin