Journal of Systems Engineering and Electronics ›› 2012, Vol. 34 ›› Issue (5): 1030-1035.doi: 10.3969/j.issn.1001-506X.2012.05.31

• 通信与网络 • 上一篇    下一篇


李振1, 孙新利1, 雷俊牛2, 姬国勋1, 刘志勇3   

  1. 1. 第二炮兵工程学院, 陕西 西安 710025;
    2. 中国人民解放军92857部队, 北京 100161;
    3. 第二炮兵装备研究院二所, 北京 100085
  • 出版日期:2012-05-23 发布日期:2010-01-03

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

LI Zhe1,SUN Xin-li1, LEI Jun-niu2, JI Guo-xun1, LIU Zhi-yong3   

  1. 1. The Second Artillery Engineering Unirersity, Xi’an 710025, China;
     2. Unit 92857 of the PLA, Beijing 100161, China|;
    3. The No.2 Institutet of Second Artillery Equipment Academy, Beijing 100085, China
  • Online:2012-05-23 Published:2010-01-03




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.