Abstract:

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.