TY - JOUR

T1 - Computing residual connectedness reliability for restricted networks

AU - Colbourn, Charles J.

AU - Satyanarayana, A.

AU - Suffel, C.

AU - Sutner, K.

N1 - Funding Information:
Research of the first author is supported in part under NSERC Canada grant A0579, research of the second author is supported in part under AR0 grant DAAL03-90-G-0078.

PY - 1993/7/19

Y1 - 1993/7/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38248999680&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38248999680&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(93)90233-E

DO - 10.1016/0166-218X(93)90233-E

M3 - Article

AN - SCOPUS:38248999680

SN - 0166-218X

VL - 44

SP - 221

EP - 232

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -