文章基本信息

标题：An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets
本地全文：下载
作者：Yan-Rui Sun ; Wei-Yi Zhou
期刊名称：American Journal of Computational Mathematics
印刷版ISSN：2161-1203
电子版ISSN：2161-1211
出版年度：2012
卷号：2
期号：4
页码：316-320
DOI：10.4236/ajcm.2012.24043
出版社：Scientific Research Publishing
摘要：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+m³+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.
关键词：Inclusion-Exclusion Formula; Network Reliability; Minimal Cutset; Dynamic Programming