Premium
Combining monte carlo estimates and bounds for network reliability
Author(s) -
Nel Louis D.,
Colbourn Charles J.
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200303
Subject(s) - monte carlo method , probabilistic logic , matroid , reliability (semiconductor) , mathematical optimization , mathematics , computer science , computational complexity theory , spanning tree , time complexity , algorithm , discrete mathematics , statistics , power (physics) , physics , quantum mechanics
A simplified model of a communications network is a probabilistic graph in which each edge operates with the same probability. The all‐terminal reliability , or probability that all nodes are connected, can be expressed as a polynomial in the edge operation probability. The coefficients of this polynomial are obtained from an interval partitioning of the cographic matroid, and only the first few coefficients can be computed efficiently. One of the best sets of efficiently computable reliability bounds is the Ball‐Provan bounds. These bounds are obtained using the efficiently computable coefficients and can be improved substantially if additional coefficients are known. In this paper, we develop a Monte Carlo method for estimating additional coefficients by randomly sampling over spanning trees of the network. Confidence intervals for all‐terminal reliability are obtained by using these estimates as additional constraints in the Ball‐Provan bounds. This approach has some advantages over conventional Monte Carlo point estimate methods. In particular, the computational complexity does not depend on the reliability of the network.