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

We investigated state space partition methods for computing probability mea sures related to the operation of stochastic systems and present new theore tical results concerning their efficiency. These methods iteratively partit ion the system state space, producing at each step progressively tighter bo unds that can be used for constructing simple and efficient Monte Carlo rou tines for estimating the probabilities of interest. We apply our findings t o the evaluation of measures related to minimum spanning trees in graphs wh ose edges have independent discrete random weights. specifically, we seek t o 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 min imum spanning tree problems are immediately applicable to other matroid pro blems with randomly weighted elements. (C) 2000 John Wiley & Sons, Inc.