Algorithm for computing multi-state network reliability based on transition of d-mincuts and d-minpaths
多状态网络可靠度的d-最小割（路）集转换算法*

This paper proposed a transition algorithm of d-mincuts and d-minpaths in order to effectively compute multi-state network reliability. Based on Boolean algebra theory, the algorithm generated all d-minpaths (d-mincuts) through expanding product-of-sum expression, with knowing all d-mincuts (d-minpaths) in advance, then calculated network reliability by app-lying inclusion-exclusion principle to d-minpaths or d-mincuts, whose amount was fewer. Furthermore, denoting a d-mincut or d-minpath through a set pair composed of unsaturated or nonzero edges and corresponding value, respectively, based on membership relationship between assembles and changing the assemble operation sequence from inverse-merging to merging inverse,proposed several lemmas to simplify algorithm. The proposed algorithm was efficient and effective, followed by the analysis of associated computational complexities. The provided example shows correctness and applicability of the algorithm.