| Communications networks, consisting of nodes interconnected by communications links, may be considered unreliable if the networks become disconnected because of failure of network components. One such model of an unreliable network is a probabilistic graph. We consider connected networks, modelled by graphs, with n nodes and m undirected links. We assume that the nodes do not fail but that links fail independently with known probabilities. The general question is, what is the probability that the network is connected? The measure that we use to consider this question is the more specific question, given two nodes, s and t, what is the probability that they are connected? This is known as the 2-terminal network reliability problem.;We are interested in a technique which has low computational complexity, with the knowledge that the 2-terminal reliability problem has been shown to be NP-Complete. Therefore, we find an approximation of the reliability by obtaining a lower bound and an upper bound on the two-terminal reliability. We suggest alternative methods of obtaining a lower bound by considering certain subsets of the set of all paths from s to t. We also suggest a method of obtaining an upper bound by considering certain subsets of the set of all cutsets from s to t. We develop heuristics to choose these subsets and in considering only subsets, we reduce the computational complexity of the problem to one that can be computed in polynomial-time, while still providing significantly accurate bounds.;We use a suite of test problems to compare the bounds resulting from our methods with bounds produced by other techniques offered in the literature, and show that our bounds offer substantial improvement. Additionally, our method provides control, with respect to execution time and accuracy. We also show that our approximate method also works significantly faster than methods to find the exact two-terminal reliability, for certain kinds of realistic networks. Thus, we provide an approximate method that results in bounds on the two-terminal reliability that is fast and accurate enough to be used in the refinement process of developing a network design. |
