Counting almost minimum cutsets with reliability applications

Aparna Ramanathan, Charles J. Colbourn

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


The number n1 of i-edge network cutsets in a graph is an important parameter in reliability analysis. Using a theorem of Lomonosov and Polesskii, Ball and Provan have shown that the number ni of minimum cardinality network cutsets can be determined in polynomial time. This paper gives a polynomial time algorithm for determining nr+k for any fixed k, as a special case of counting cuts of specified maximum weight in an edge-weighted graph. The resulting improvement in existing reliability bounds is shown to be substantial.

Original languageEnglish (US)
Pages (from-to)253-261
Number of pages9
JournalMathematical Programming
Issue number3
StatePublished - Oct 1 1987
Externally publishedYes


  • Cutset
  • inclusion-exclusion
  • network reliability
  • polynomial time
  • probabilistic graph
  • weighted graph

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Counting almost minimum cutsets with reliability applications'. Together they form a unique fingerprint.

Cite this