Abstract The purpose of this article is to introduce several results concerning the analysis and synthesis of reliable or invulnerable networks. First, the notion of signed reliability domination of systems is described and some applications to reliability analysis are reviewed. Then the analysis problem is considered and a brief summary of the difficulty of calculating various reliability measures is presented. Some relevant concepts in the synthesis of a most reliable network are studied. The article concludes with an introduction to a non‐probabilistic approach to evaluate the vulnerability of a network. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

In an original and very interesting paper (Satyanarayana and Wood [1]) concerning polygon-to-chain reductions in a stochastic network, a small inconsistency occurs in the proof of Theorem 1. In particular, this happens in cases where the whole set of ${\bf K}$-vertices lies in the remaining polygon. Such an example is the case of polygon type 5, where the appropriate note has been made by the authors for $|{\bf K}| = 2$. Analogous notes must also be made for polygon types 4, 6, and 7, when ${\bf K} = 2,3$, and 4, respectively. The correct transformations are given in Table 1 (note that dark vertices are ${\bf K}$-vertices).

Abstract This paper characterizes a class 𝒢 of partial 4‐trees in terms of a set of seven forbidden minors. The class 𝒢 contains several known classes of graphs, including both Δ ‐ Y and Y ‐ Δ graphs. A set of six graph reduction operations is defined, and it is shown that a graph G ∈ 𝒢 iff G can be reduced to an edgeless graph by a finite sequence of these operations. The all‐terminal reliability R(G) of a graph G is the probability that G is connected. The characterization of 𝒢 is used to develop an O(n log n) algorithm to compute R(G) for all n‐point graphs in 𝒢. The running time is O(n) for planar graphs in 𝒢.

Abstract This paper considers a probabilistic graph in which the points are perfectly reliable but the edges operate independently of one another, all with some known probability p. The graph G is in an operating state if the surviving edges induce a spanning connected subgraph of G. The all‐terminal reliability R(G,p) of G is the probability that G is in an operating state. A graph transformation, called “the swing surgery,” is introduced, and it is shown that this surgery has important properties. First, if H is the graph obtained by deleting m independent edges from the complete graph, then for any other graph G with the same number of points and edges as H, R(H,p) > R(G,p) for all 0 < p < 1. Moreover, the swing surgery yields a simple topological proof of the well‐known result that H has more spanning trees than does G. Another important consequence is that given any graph G there exists a threshold graph T with the same number of points and edges as G such that R(T,p) ≤ R(G,p) for all 0 < p < 1.

This paper considers 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. It is proven that the problem of computing the residual connectedness reliability is NP-hard by showing that the problem of counting the number of node induced connected subgraphs of a given graph is $# {\bf P}$-complete. The problem remains $# {\bf P}$-complete for split graphs as well as planar and bipartite graphs.

Abstract A k‐tree is defined recursively as follows: The complete graph Kk on k points is a k‐tree. Given a k‐tree G on n ≤ k points, a k‐tree on n + 1 points is obtained by adding a new point u and edges connecting u to every point of a Kk in G. A graph is a partial k‐tree if it is a subgraph of some k‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible to K5, K2.2.2 C8(1, 4), or K2 ≤ C5. A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. hitherto, such a characterization of partial k‐trees was known only for the values of k ≤ 2.

A well-known model in communication network reliability consists of an undirected graph G whose edges operate independently with the same probability p. Then the reliability, R(G,p) of G, is the probability that G is connected. It is known that R(G,p) is a polynomial in p and its coefficient of the least-order term is the number of spanning trees t(G), while the coefficient of the highest-order term is the reliability domination d(G) of G. Presented is a complete characterization of graphs that achieve the minimum absolute value mod d(G) mod over the class of n-node, e-edge connected graphs. Furthermore, the class of graphs that yield minimum t(G) is shown to minimize mod d(G) mod . The results have applications in the synthesis of least-reliable networks.>

Abstract The problem of computing the SKT reliability, the probability that a source s can send communication to a specified set of terminals K ⊂ V in a probabilistic digraph D = (V,E) is considered. For general digraphs, this problem is known to be NP‐hard and it is helpful to consider schemes that can decompose the problem into a number of smaller problems. A non‐separable digraph is 2‐connected if it contains a separation pair, a pair of nodes whose removal disconnects the digraph. Such a digraph can be partitioned into two or more segments. It is shown that at least one of these segments can be replaced by a simpler structure; this replacement results in an exact reliability preserving reduction. The proposed reduction scheme is general and is applicable to all digraphs containing a separation pair; earlier methods could only handle special cases. For a class of digraphs, called BSP digraphs, such a reduction is always admissible and the SKT reliability can be computed in time O(∣ E ∣). A digraph is a BSP digraph if its underlying undirected graph is series‐parallel. A BSP digraph can be cyclic or acyclic. No polynomial‐time algorithms were previously known for this class of digraphs.

Let $G = (V,E)$ be a graph whose edges may fail with known probabilities and let $K \subseteq V$ be specified. The K-terminal reliability of G, denoted $R(G_K )$, is the probability that all vertices in K are connected. Computing $R(G_K )$ is, in general, NP-hard. For some series-parallel graphs, $R(G_K )$ can be computed in polynomial time by repeated application of well-known reliability-preserving reductions. However, for other series-parallel graphs, depending on the configuration of K, $R(G_K )$ cannot be computed in this way. Only exponential-time algorithms as used on general graphs were known for computing $R(G_K )$ for these “irreducible” series-parallel graphs. We prove that $R(G_K )$ is computable in polynomial time in the irreducible case, too. A new set of reliability-preserving “polygon-to-chain” reductions of general applicability is introduced which decreases the size of a graph, and conditions are given for a graph admitting such reductions. Combining all types of reductions, an $O(|E|)$ algorithm is presented for computing the reliability of any series-parallel graph irrespective of the vertices in K.