Premium
Efficient algorithms for computing the reliability of permutation and interval graphs
Author(s) -
Aboeifotoh Hosam M.,
Colbourn Charles J.
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200706
Subject(s) - chordal graph , interval graph , indifference graph , computer science , probabilistic logic , reliability (semiconductor) , permutation (music) , mathematics , discrete mathematics , algorithm , theoretical computer science , combinatorics , graph , 1 planar graph , power (physics) , physics , quantum mechanics , artificial intelligence , acoustics
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.