Efficient algorithms for computing the reliability of permutation and interval graphs

Hosam M. Aboeifotoh, Charles J. Colbourn

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


A stochastic network in which nodes fail randomly with known probabilities is modeled by a probabilistic graph with unreliable nodes and perfect edges. The K‐terminal reliability of such a network is the probability that there exists a Steiner tree connecting a subset of the nodes K (target nodes). Although the K‐terminal reliability problem has been widely studied for networks with unreliable links, very little is known about the problem for networks with unreliable nodes. We show that computing this measure is computationally difficult, in particular #P‐complete. We then present efficient algorithms for the K‐terminal reliability problem on two classes of perfect graphs; interval graphs and permutation graphs. Computing the reliability on these two classes of graphs is of particular interest since the problem remains #P‐complete for larger classes in the hierarchy of perfect graphs, namely, comparability and chordal graphs. The model presented in this paper is appropriate for radio broadcast networks and for fault‐tolerant multiprocessor networks.

Original languageEnglish (US)
Pages (from-to)883-898
Number of pages16
Issue number7
StatePublished - Dec 1990
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this