Computing network reliability using exact and Monte Carlo methods

In this dissertation we consider several topics in network reliability. The networks under consideration are undirected graphs with perfectly reliable vertices and have edges that are subject to independent failures. Edge reliabilities are assumed to be known. The network reliability problem we study is to evaluate the probability that a specified subset of vertices is connected by working edges. In chapter 1, concepts from graph theory and computational complexity and the relevant literature of network reliability are reviewed.;A common approach in network reliability analysis is to use reliability- preserving reductions either alone or in conjunction with other methods. In chapter 2, we establish a framework to devise reliability-preserving reductions. We use this framework to derive new expressions for the extended ;Another well known approach to network reliability analysis is the use of factoring algorithms. In chapter 3, we present a FORTRAN implementation of a factoring algorithm that makes use of series, parallel and degree-2 reductions as well as an optimal edge selection strategy. This program is used to evaluate the ideas introduced in chapters 4 and 5.;The effect of reliability-preserving reductions prior to the use of a Monte Carlo method is analyzed in chapter 4. We find that the use of these reductions not only reduces the time per simulation trial but often also reduces the number of trials necessary to achieve a certain level of accuracy. Numerical results are presented. A Bayesian approach is used for the Monte Carlo method providing new insight into the process of estimation of network reliability.;A hybrid algorithm for computing network reliability which combines a factoring algorithm with a Monte Carlo method is constructed in chapter 5. Numerical results are presented for individual heuristics incorporated in the algorithm, as well as for the hybrid algorithm as a whole.