A new algorithm for generating minimal cut sets in k-out-of-n networks

Wei-Chang Yeh

Reliability Engineering and System Safety, 2006, vol. 91, issue 1, 36-43

Abstract: Evaluating the network reliability is an important topic in the planning, designing, and control of systems. A k-out-of-n network is a special network in that some nodes must receive at least k (>1) flows from all of their input edges (n). In real-life cases, many networks such as computer and telecommunications include k-out-of-n nodes for redundancy. The minimal-cut-node-set (MCN) is the major and fundamental tools for evaluating the k-out-of-n network reliability. In this study, a very simple algorithm based on some intuitive theorems that characterize the structure of the MCN is developed to solve the k-out-of-n network reliability. Compared to the existing algorithms, the proposed algorithm generates all k-out-of-n MCs without duplication based on fewer MCNs and fewer (k-out-of-n MC) candidates. The proposed algorithm is not only easier to understand and implement, but is also better than the existing algorithms. The correctness of the proposed algorithm will be analyzed and proven. One example is illustrated to show how all k-out-of-n MCs are generated, verified, and implemented to evaluate the k-out-of-n network reliability using the proposed algorithm.

Keywords: Network; Reliability; k-out-of-n; Minimal-cut-node set (MCN); Algorithm (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832005000104
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:91:y:2006:i:1:p:36-43

DOI: 10.1016/j.ress.2004.11.020

Access Statistics for this article

Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares

More articles in Reliability Engineering and System Safety from Elsevier
Bibliographic data for series maintained by Catherine Liu ().