An improved algorithm for searching all minimal cuts in modified networks

An improved algorithm for searching all minimal cuts in modified networks

0.00 Avg rating0 Votes
Article ID: iaor20103741
Volume: 93
Issue: 7
Start Page Number: 1018
End Page Number: 1024
Publication Date: Jul 2008
Journal: Reliability Engineering and System Safety
Authors:
Abstract:

A modified network is an updated network after inserting a branch string (a special path) between two nodes in the original network. Modifications are common for network expansion or reinforcement evaluation and planning. The problem of searching all minimal cuts (MCs) in a modified network is discussed and solved in this study. The existing best-known methods for solving this problem either needed extensive comparison and verification or failed to solve some special but important cases. Therefore, a more efficient, intuitive and generalized method for searching all MCs without an extensive research procedure is proposed. In this study, we first develop an intuitive algorithm based upon the reformation of all MCs in the original network to search for all MCs in a modified network. Next, the correctness of the proposed algorithm will be analyzed and proven. The computational complexity of the proposed algorithm is analyzed and compared with the existing best-known methods. Finally, two examples illustrate how all MCs are generated in a modified network using the information of all of the MCs in the corresponding original network.

Reviews

Required fields are marked *. Your email address will not be published.