Computing residual connectedness reliability for restricted networks

Charles J. Colbourn, A. Satyanarayana, C. Suffel, K. Sutner

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


We consider a probabilistic network in which the edges are perfectly reliable but the nodes fail with some known probabilities. The network is in an operational state if the surviving nodes induce a connected graph. The residual node connectedness reliability R(G) of a network G is the probability that the graph induced by the surviving nodes is connected. This reliability measure is very different from the widely studied K-terminal network reliability measure. In a recent work, the problem of computing the residual connectedness reliability has been shown to be NP-hard. The problem remains NP-hard for split graphs as well as planar and bipartite graphs. This paper presents efficient algorithms for computing R(G) of various restricted classes of networks. The classes that admit polynomial time algorithms include trees, series-parallel graphs, partial k-trees, directed path graphs and permutation graphs. Suppose c is a positive integer and Gn,c is the collection of all graphs G on n points such that every induced subgraph of G on k points has maximum degree at least k-c-l. We show that R(G) is computable in O(n2) time. An important consequence of this result is that R(G) is efficiently computable whenever G is the complement of a planar graph G.

Original languageEnglish (US)
Pages (from-to)221-232
Number of pages12
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Jul 19 1993
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Computing residual connectedness reliability for restricted networks'. Together they form a unique fingerprint.

Cite this