Exact graph-reduction algorithms for network reliability analysis

We consider the problem of analyzing the reliability of a network, specifically, the probability that a given set of critical nodes within the network can communicate, given the failure probabilities for component nodes and links. This is important for network management as it identifies when a network needs to be reinforced to provide adequate reliability. It is also important in planning topological modifications to a network.;This thesis presents an exact graph-reduction algorithm for solving the k-terminal reliability problem with node failures on an arbitrary network. k-terminal reliability means that a specific set of k target nodes must be able to communicate with one another. We model the network by an undirected probabilistic graph whose vertices represent the nodes and whose edges represent the links. A special feature of our model is that it allows nodes to be imperfect and associates a reliability measure with each node, assumed to succeed or fail independently. Therefore, the network reliability measure is based upon the reliability measures of the individual links and nodes.;The k-terminal reliability problem is known to be NP-complete. However, for a limited set of networks, it is possible to calculate the k-terminal reliability in polynomial time. We extend the Delta-Y and the Polygon-Chain graph transformations to operate on k-terminal reliability graphs with imperfect vertices. We present an algorithm which calculates the k-terminal reliability faster than Satyanarayana and Wood's algorithm and characterize that set of networks for which our computation takes polynomial time.