Network transformations and bounding network reliability

Jason I. Brown, Charles J. Colbourn, John S. Devitt

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


Three transformations on networks that reduce the all‐terminal network reliability (probability of connectedness) of a network are shown not to increase any coefficient in one form of the reliability polynomial of the network. These transformations yield efficiently computable lower bounds on each coefficient of the reliability polynomial. A further transformation due to Lomonosov is shown not to decrease any coefficient in the reliability polynomial, leading to an efficiently computable upper bound on each coefficient. The resulting bounds on coefficients can, in turn, be used to obtain a substantial improvement on the Ball—Provan strategy for computing lower and upper bounds on the all‐terminal reliability. © 1993 John Wiley & Sons, Inc.

Original languageEnglish (US)
Pages (from-to)1-17
Number of pages17
Issue number1
StatePublished - Jan 1993
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Network transformations and bounding network reliability'. Together they form a unique fingerprint.

Cite this