An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets
An Inclusion-Exclusion Algorithm for Network Reliability with Minimal Cutsets作者机构：School of Electronic Information Wuhan University Wuhan China School of Sciences Northeastern University Shenyang China
出 版 物：《American Journal of Computational Mathematics》 (美国计算数学期刊（英文）)
年 卷 期：2012年第2卷第4期
页 面：316-320页
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：Inclusion-Exclusion Formula Network Reliability Minimal Cutset Dynamic Programming
摘 要：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.
维普期刊数据库