Bounding distributions for the weight of a minimum spanning tree in stochastic networks
成果类型：
Article
署名作者：
Hutson, KR; Shier, DR
署名单位：
University System of Ohio; Denison University; Clemson University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1050.0214
发表日期：
2005
页码：
879-886
关键词：
摘要：
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.