Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks

This paper considers the problem of determining the distribution of the weight W of a minimum spanning tree for an undirected graph with edge weights that are independently distributed discrete random variables. Using the underlying fundamental cutsets and cycles associated with a spanning tree, we are able to obtain upper and lower bounds on the distribution of W. In turn, these are used to establish bounds on E[W]. Our general method for deriving these bounding distributions subsumes existing approximation methods in the literature. Computational results indicate that the new approximation methods provide excellent bounds for some challenging test networks.