Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
Report ID: TR-289-90Author: Dixon, Brandon / Rauch, Monika / Tarjan, Robert E.
Date: 1990-07-00
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.