多状态网络系统d-最小割集的边合并算法

为更有效的获取多状态网络系统d-最小割集（d-mincuts,d-MCs）,提出一种边合并算法。算法用容量未取最大容量的边及对应取值组成的集合对表示网络状态,基于网络分割的思想,不以最小割集为基础,通过边合并、状态继承求取可行解,通过集合对的比较得到d-MCs。同时提出一个引理,更高效的求取容量下界,缩小状态空间。算法复杂度对比分析证明算法有效,且通过定义带权值的广义联络矩阵实现算法,便于编程计算。最后,通过实例分析验证了算法的有效性。

Edge merging algorithm for enumerating d-mincuts of multi-state network

In order to obtain d-mincuts(d-MCs) of a multi-state network more effectively,an edge merging algorithm is proposed.A network state is defined through a set pair consisting of unsaturated edges and corresponding value.Based on the network partition theorem,the algorithm generates all candidates through edge merging and state inheriting without knowing all minimal cuts in advance,then d-MCs by comparison of set pairs are obtained.Furthermore,one lemma is proposed to more effectively calculate the infimum of the capacity so as to reduce state space.The proposed algorithm is demonstrated more effectively by the analysis and comparison of associated computational complexities.Further,it can be implemented simply by the definition of the extended adjacent matrix with weight.The provided example illustrates the effectiveness of the algorithm.