Combinatorial methods in network reliability analysis

In this paper, a stochastic network is an undirected graph with unreliable edges and absolutely reliable nodes. Its connectedness probability is determined by reliability preserving network reduction. The principle of this method consists in splitting the underlying deterministic graph of the stochastic network into two edge-disjoint subgraphs via a separating node set. One of the subgraphs is replaced with a simpler structured graph (replacement graph) in such a way that the interesting reliability criterion of the original stochastic network is retained. Special attention is given to the construction of suitable replacement graphs. The case of a 3-point separating node set is considered in more detail.