Combining monte carlo estimates and bounds for network reliability

Louis D. Nel, Charles J. Colbourn

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)277-298
Number of pages22
Issue number3
StatePublished - May 1990
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Combining monte carlo estimates and bounds for network reliability'. Together they form a unique fingerprint.

Cite this