Exact Graph-Redu et ion 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.