Exact Methods to Compute Network Reliability
Corinne Lucet, Jean-François Manouvrier · Birkhäuser Boston eBooks · 1999
In this chapter we present and compare some exact methods to resolve network reliability problems. These problems concern all kinds of networks, such as computer, communication or power networks. When components of the network are subject to random failures, the network may or may not continue functioning after the failures of some components. The probability that the network will function is its reliability. Networks are modeled by a graph G = ( V , E ) composed of elements that fail independently one another with known probabilities. The K-terminal reliability problem has been studied extensively. It consists in evaluating the probability that a given subset of vertices, denoted K, is connected. This problem is NP-hard. We propose here to present the main methods, developed since the 1970s. We first consider the enumeration methods using elementary states, paths or cuts. Then we explain the factoring method performed by reductions. These allow to handle series-parallel graphs to be processed in linear time. Finally, we present the decomposition method implemented as a table-based reduction algorithm allowing to resolve the reliability problem in linear time for graphs with bounded pathwidth.