IMPROVING BOUNDS FOR ALL-TERMINAL NETWORK RELIABILITY

A standard model of a network is a graph in which nodes represent communication centers and edges represent links between these centers. Edges are assumed to have statistically independent probabilities of failure, and nodes are assumed to be perfectly reliable. The all-terminal reliability of the network is defined to be the probability that all the communication centers in the network are able to communicate with each other in an environment of random link failures. Exact calculation of the all-terminal reliability for general graphs is known to be ;In this thesis, two different methods are developed to improve on the existing bounds. Firstly, a new polynomial time algorithm to count almost minimal cutsets provides immediate improvement on all of the subgraph counting bounds. Improvements on the bounds for planar networks are also derived by using a result by Liu and Chow to compute some additional coefficients in the reliability polynomial. A substantial improvement in Kruskal-Katona bounds and a new version of Ball-Provan bounds are derived.;The second method uses arc-disjoint rooted subdigraphs of a network to improve on existing lower bounds and arc-disjoint s -directed cuts for upper bounds. Different techniques to obtain arc-disjoint acyclic subdigraphs are developed, and appropriate choices of subdigraphs are discussed. The lower bounds obtained from an arc-packing of acyclic rooted subdigraphs are shown to be competitive both with the Kruskal-Katona and Lomonosov-Polesskii bounds. The upper bound obtained from any arc-packing of s -directed cuts is shown to be no better than the Lomonosov-Polesskii upper bound.;In summary, we establish four main results. Knowing some additional coefficients provides a dramatic improvement in the subgraph counting bounds. Additional coefficients can be efficiently calculated by counting almost-minimum cutsets. Packing a directed graph with rooted acyclic subdigraphs provides a powerful new technique to obtain lower bounds. Finally, the upper bound obtained by taking any arc-packing of s -directed cuts does not provide improvement over Lomonosov-Polesskii upper bound.