This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Hutson, K. R. Articles by Shier, D. R. Search for Related Content

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

Department of Mathematics and Computer Science, Denison University, Granville, Ohio 43023
Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634
hutsonk{at}denison.edu
shierd{at}clemson.edu

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.

Subject classifications: stochastic networks: bounding distributions for minimum spanning tree weight; tree algorithms: fundamental cycles and cutsets.
History: Received November 2002; revision received December 2003; revision received August 2004; accepted September 2004.