An optimal minimum spanning tree algorithm
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically. we present a deterministic algorithm to find a minimum spanning tree of a graph within vertices and m edges that runs in time O(T*(m, n)) where T* is the minimum number of edge-weight comparisons needed to determine the solution. The algorithm is quite simple and can be implemented on a pointer machine. Although our time bound is optimal, the exact function describing it is not known at present. The current best bounds known for T* are T*(m, n) = Omega(m) and T*(m, n) = O(m - alpha(m, n)), where alpha is a certain natural inverse of Ackermann's function, Even under the assumption that T(-) is superlinear, we show that if the input graph is selected front G(n,m), our algorithm runs in linear time with high probability, regardless of n, in, or the permutation of edge weights. The analysis uses a new martingale for G(n,m), similar to the edge-exposure martingale for G(n,p).
minimum spanning tree algorithms theory graph algorithms optimal complexity