TITLE:
An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets
AUTHORS:
Yan-Rui Sun, Wei-Yi Zhou
KEYWORDS:
Inclusion-Exclusion Formula; Network Reliability; Minimal Cutset; Dynamic Programming
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.2 No.4,
December
25,
2012
ABSTRACT: The inclusion-exclusion formula (IEF) is a fundamental tool for evaluating network reliability with known minimal paths or minimal cuts. However, the formula contains many pairs of terms which cancel. Using the notion of comparable node partitions some properties of canceling terms in IEF are given. With these properties and the thought of “dynamic programming” method, a simple and efficient inclusion-exclusion algorithm for evaluating the source-to-terminal reliability of a network starting with cutsets is presented. The algorithm generates all the non-canceling terms in the unreliability expression. The computational complexity of the algorithm is O(n+m3+M), where n and m are the numbers of nodes and minimal cuts of the given network respectively, M is the number of terms in the final symbolic unreliability expression that generated using the presented algorithm. Examples are shown to illustrate the effectiveness of the algorithm.