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

Kevin R. Hutson () and Douglas R. Shier ()
Additional contact information
Kevin R. Hutson: Department of Mathematics and Computer Science, Denison University, Granville, Ohio 43023
Douglas R. Shier: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634

Operations Research, 2005, vol. 53, issue 5, 879-886

Abstract: 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.

Keywords: stochastic networks: bounding distributions for minimum spanning tree weight; tree algorithms: fundamental cycles and cutsets (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1050.0214 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:53:y:2005:i:5:p:879-886

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().