Calculating bounds on reachability and connectedness in stochastic networks

Abstract In this article, computational procedures are presented for generating bounds on measures of network reliability. The two measures considered, reachability and connectedness, are the probability that there is an operating path from a node to all other nodes in a directed (respectively undirected) stochastic network. Our bounds, which are given in terms of polynomials in p , the common arc failure probability, are based on recent bounding results developed by the authors for the class of shellable independence systems. Two pairs of bounds are given: weaker bounds whose computation time is bounded by a polynomial in the size of the network and tighter bounds whose computation time is bounded by a polynomial in the size of the network and the number of minimum‐cardinality network cuts. Computational results are also given which evaluate the quality of the bounds. The generation of the bounds involves several interesting path and cut counting problems.