An optimal minimum spanning tree algorithm

Abstract

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 with n 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 ) = Ω( m ) and T * ( m,n ) = O ( m ∙ α( m,n )), where α 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 from G n,m , our algorithm runs in linear time with high probability, regardless of n , m , 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 .