Abstract. Koml os 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 Koml os 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. 1. Introduction. Suppose we wish to solve some problem for which we know in advance the size of the input data, using an algorithm from some well-dened class of algorithms. For example, consider sorting n numbers, when n is xed in advance, using a binary comparison tree. Given a sucient amount of preprocessing time and storage space, we can in a preprocessing step compute a minimum-depth comparison tree, store it explicitly, and then solve any instance of the sorting problem by using the precomputed comparison tree. This technique is of course generally useless because it is prohibitively expensive in preprocessing time and storage space, both being at least exponential in n. There are situations in which this idea can be used to advantage, however. This is the case in problems susceptible to very ecient divideand-conquer. The idea is to split the problem to be solved into subproblems, which are categorized into classes. If the subproblems are small enough, they can be solved eciently as follows: An optimal algorithm for each class is precomputed and stored in a look-up table, and each instance of a subproblem is solved by looking up and running the algorithm for its class. For this technique to pay o, solving all the subproblems must reduce the original problem suciently that it can be solved quickly with respect to the size of the original problem by using a non-optimal algorithm. This paper presents an applicationof this general techniqueto two problems concerningminimum spanning trees. This approach was rst proposed explicitly by Larmore [15], who used it to solve a convex matrix searching problem. Related techniques were used by Gabow and Tarjan [8] to solve a disjoint set union problem, by Harel and Tarjan [12] to nd nearest common ancestors in a tree, and by Fredman [5] to solve the all pairs shortest path problem. We present an algorithm that veries a minimum spanning tree in an n-vertex, m-edge graph in O(m) time. We also give algorithms performing sensitivity analysis of minimum spanning trees in worst-case time minimum to within a constant factor and in linear expected time. Our model of computation allows edge costs to be compared, added, or subtracted at unit cost, and side computations to be performed on a unit-cost random-access machine with word size (logn) bits. The verication algorithm uses the comparison bound of Koml os [14] for the subproblems and Tarjan's O(m(m; n)) algorithm [17] for the reduced problem. For sensitivity analysis we solve the subproblems using a result of Goddard, King, and Schulman [9] in the randomized case and enumeration of all possible algorithms in the deterministic case. In both cases Tarjan's O(m(m; n))-time sensitivity analysis algorithm [18] processes the reduced problem. We describe the algorithms in Sections 2 and 3. Section 4 contains concluding remarks. It is important to note that our computational model allows only very simple operations on the edge costs, namely binary comparison, addition, and subtraction. In a more powerful model in which bit manipulation of the edge costs is possible, better results can be obtained using table lookup and other ideas. In particular, Harel [11] showed that if the edge costs are integers polynomially boundedin n , then on a unit-costrandom-accessmachine the minimum spanningtree vericationand sensitivity analysis problems can be solved deterministically in linear time. More recently Fredman and Willard [6] showed that if the edge costs are single-precision integers, then a minimum spanning a
Using this connection, in a model where edge weights are atomic, but side-computations on a RAM are allowed, all the best swap edges can be found in O(m) expected time using a randomized algorithm given by Dixon et al. REF .
Verification and Sensitivity Analysis Of Minimum Spanning Trees In Linear Time
SIAM J. Comput
Mathematics Computer Science