State space partition algorithms for stochastic systems with applications to minimum spanning trees

State space partition algorithms for stochastic systems with applications to minimum spanning trees

0.00 Avg rating0 Votes
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: ,
Keywords: minimum spanning trees
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.