Article ID: | iaor20022977 |
Country: | United States |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 118 |
End Page Number: | 138 |
Publication Date: | Jan 2000 |
Journal: | Networks |
Authors: | Alexopoulos Christos, Jacobson Jay A. |
Keywords: | minimum spanning trees |
We investigated state space partition methods for computing probability measures related to the operation of stochastic systems and present new theoretical results concerning their efficiency. These methods iteratively partition the system state space, producing at each step progressively tighter bounds that can be used for constructing simple and efficient Monte Carlo routines for estimating the probabilities of interest. We apply our findings to the evaluation of measures related to minimum spanning trees in graphs whose edges have independent discrete random weights. Specifically, we seek to compute the distribution of the weight of a minimum spanning tree and the probability that a given edge belongs to a minimum spanning tree. Both of these unsolved problems are shown to be #P-hard. The algorithms for the minimum spanning tree problems are immediately applicable to other matroid problems with randomly weighted elements.