Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

Abstract

. Koml'os has devised a way to use a linear number of binary comparisons to testwhether a given spanning tree of a graph with edge costs is a minimum spanning tree. The totalcomputational work required by his method is much larger than linear, however. We describe alinear-time algorithm for verifying a minimum spanning tree. Our algorithm combines the result ofKoml'os with a preprocessing and table look-up method for small subproblems and with a previouslyknown almost-linear-time...