Lower bounds on two-terminal network reliability

Timothy B. Brecht, Charles J. Colbourn

Research output: Contribution to journalArticlepeer-review

74 Scopus citations


Computing the probability that two nodes in a probabilistic network are connected is a well-known computationally difficult problem. Two strategies are devised for obtaining lower bounds on the connection probability for two terminals. The first improves on the Kruskal-Katona bound by using efficient computations of small pathsets. The second strategy employs efficient algorithms for finding edge-disjoint paths. The resulting bounds are compared; while the edge-disjoint path bounds typically outperform the Kruskal-Katona bounds, they do not always do so. Finally, a method is outlined for developing a uniform bound which combines both strategies.

Original languageEnglish (US)
Pages (from-to)185-198
Number of pages14
JournalDiscrete Applied Mathematics
Issue number3
StatePublished - Oct 1988
Externally publishedYes


  • Network reliability
  • efficient algorithm
  • reliability bound
  • topological design
  • two-terminal reliability

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Lower bounds on two-terminal network reliability'. Together they form a unique fingerprint.

Cite this