Communications - Scientific Letters of the University of Zilina 2015, 17(4):8-14 | DOI: 10.26552/com.C.2015.4.8-14

Evaluation of Algorithms for Identification of Minimal Cut Vectors and Minimal Path Vectors in Multi-State Systems

Miroslav Kvassay1, Jozef Kostolny1
1 Department of Informatics, Faculty of Management Science and Informatics, University of Zilina, Slovakia

Minimal Cut Vectors (MCVs) and Minimal Path Vectors (MPVs) are one of the key concepts of reliability analysis. They allow us to estimate system availability or to analyze influence of individual system components on the entire system. However, the main problem of their use, especially in reliability analysis of complex systems, lies in their identification. Several algorithms have been proposed to solve this task. Some of the most universal ones are based on logical differential calculus. These algorithms use integrated direct partial logic derivatives to find situations that can correspond to the MCVs (MPVs) and a special type of logic conjunction to select only those situations that really agree with the MCVs (MPVs). In this paper, we summarize the ideas behind these algorithms in more formal way and present results of some experiments performed to study their time complexity.

Keywords: reliability; multi-state system; minimal cut vector; minimal path vector; direct partial logic derivative; integrated direct partial logic derivative

Published: December 31, 2015  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Kvassay, M., & Kostolny, J. (2015). Evaluation of Algorithms for Identification of Minimal Cut Vectors and Minimal Path Vectors in Multi-State Systems. Communications - Scientific Letters of the University of Zilina, 17(4), 8-14. doi: 10.26552/com.C.2015.4.8-14
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. EISENBERG, N. A., SAGAR, B.: Importance Measures for Nuclear Waste Repositories, Reliability Engineering & System Safety, vol. 70, No. 3, pp. 217-239, 2000. Go to original source...
    2. RADOS, I., SCHWARTZ, L.: The Worst Availability as a Parameter for Designing and Reporting on the Network Performances, Communications - Scientific Letters of the University of Zilina, vol. 13, No. 1, pp. 60-66, 2011. Go to original source...
    3. BRIS, R.: Assessment of the Availability of an Offshore Installation by Stochastic Petri Net Modeling, Communications - Scientific Letters of the University of Zilina, vol. 16, No. 1, pp. 90-96, 2014. Go to original source...
    4. ZAITSEVA, E., KVASSAY, M., LEVASHENKO, V., KOSTOLNY, J.: Reliability Analysis of Logic Network with Multiple Outputs, Communications - Scientific Letters of the University of Zilina, vol. 17, No. 1A, pp. 44-50, 2015. Go to original source...
    5. ZAITSEVA, E., LEVASHENKO, V., RUSIN, M.: Reliability Analysis of Healthcare System, 2011 Federated Conference on Computer Science and Information Systems, FedCSIS 2011, 2011, pp. 169-175.
    6. PRAKS, P., KOPUSTINSKAS, V.: Monte-Carlo Based Reliability Modelling of a Gas Network Using Graph Theory Approach, Ninth Intern. Conference on Availability, Reliability and Security, 2014, pp. 380-386. Go to original source...
    7. ZIO, E.: Reliability Engineering: Old Problems and New Challenges, Reliability Engineering & System Safety, vol. 94, No. 2, pp. 125-141, 2009. Go to original source...
    8. RAUSAND M., HOYLAND, A.: System Reliability Theory, 2nd ed., Haboken: John Wiley & Sons, 2004.
    9. LISNIANSKI, A., FRENKEL, I., DING, Y.: Multi-state System Reliability Analysis and Optimization for Engineers and Industrial Managers. London : Springer-Verlag, 2010. Go to original source...
    10. NATVIG, B.: Multistate Systems Reliability Theory with Applications. Chichester : John Wiley & Sons 2011. Go to original source...
    11. KUO, W., ZHU, X.: Importance Measures in Reliability, Risk, and Optimization: Principles and Applications. Chichester : Wiley, 2012. Go to original source...
    12. KVASSAY, M., ZAITSEVA, E., LEVASHENKO, V.: Minimal Cut Sets and Direct Partial Logic Derivatives in Reliability Analysis, Safety and Reliability: Methodology and Applications, Proc. of the European Safety and Reliability Conference, ESREL 2014, 2015, pp. 241-248.
    13. VATN, J.: Finding Minimal Cut Sets in a Fault Tree, Reliability Engineering & System Safety, vol. 36, No. 1, pp. 59-62, 1992. Go to original source...
    14. RAUZY, A.: New Algorithms for Fault Trees Analysis, Reliability Engineering & System Safety, vol. 40, No. 3, pp. 203-211, 1993. Go to original source...
    15. SINNAMON R. M., ANDREWS, J. D.: New Approaches to Evaluating Fault Trees, Reliability Engineering & System Safety, vol. 58, No. 2, pp. 89-96, 1997. Go to original source...
    16. SHEN, Y.: A New Simple Algorithm for Enumerating All Minimal Paths and Cuts of a Graph, Microelectronics Reliability, vol. 35, No. 6, pp. 973-976, 1995. Go to original source...
    17. YEH, W.-C.: Search for all MCs in Networks with Unreliable Nodes and Arcs, Reliability Engineering & System Safety, vol. 79, No. 1, pp. 95-101, 2003. Go to original source...
    18. EMADI, A., AFRAKHTE, H.: A Novel and Fast Algorithm for Locating Minimal Cuts up to Second Order of Undirected Graphs with Multiple Sources and Sinks, Intern. J. of Electrical Power & Energy Systems, vol. 62, pp. 95-102, 2014. Go to original source...
    19. YEH, W.-C.: A New Approach to the d-MC Problem, Reliability Engineering & System Safety, vol. 77, No. 2, pp. 201-206, 2002. Go to original source...
    20. YEH, W.-C.: The Extension of Universal Generating Function Method to Search for All One-to-Many d-Minimal Paths of Acyclic Multi-State-Arc Flow-Conservation Networks, IEEE Transactions on Reliability, vol. 57, No. 1, pp. 94-102, 2008. Go to original source...
    21. YEH, W.-C.: A Fast Algorithm for Searching All Multi-state Minimal Cuts, IEEE Transactions on Reliability, vol. 57, No. 4, pp. 581-588, 2008. Go to original source...
    22. KVASSAY, M., ZAITSEVA, E., LEVASHENKO, V., KOSTOLNY, J.: Minimal Cut Vectors and Logical Differential Calculus, 2014 IEEE 44th Intern. Symposium on Multiple-Valued Logic, 2014, pp. 167-172. Go to original source...
    23. KVASSAY, M., ZAITSEVA, E.: Construction of Healthcare System Structure for Reliability Analysis, 2014 Federated Conference on Computer Science and Information Systems, FedCSIS 2014, 2014, vol. 2, pp. 191-199. Go to original source...
    24. YANUSHKEVICH, S. N., MILLER, D. M., SHMERKO, V. P., STANKOVIC, R. S.: Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook, vol. 2, Boca Raton: CRC Press, 2005.
    25. ZAITSEVA, E. N., LEVASHENKO, V. G.: Importance Analysis by Logical Differential Calculus, Automation and Remote Control, vol. 74, No. 2, pp. 171-182, 2013. Go to original source...
    26. ZAITSEVA, E., LEVASHENKO, V.: Multiple-valued Logic Mathematical Approaches for Multi-state System Reliability Analysis, J. of Applied Logic, vol. 11, No. 3, pp. 350-362, 2013. Go to original source...
    27. ZAITSEVA, E., LEVASHENKO, V.: Multi-state System Analysis based on Multiple-valued Decision Diagram, J. of Reliability and Statistical Studies, vol. 5, No. Special, pp. 107-118, 2012.
    28. BOEDIGHEIMER, R. A., KAPUR, K. C.: Customer-driven Reliability Models for Multistate Coherent Systems, IEEE Transactions on Reliability, vol. 43, No. 1, pp. 46-50, 1994. Go to original source...
    29. KVET, M., VAJSOVA, M., MATIASKO, K.: Complex Data Management in MRI Results Processing, in Applications of Computational Intelligence in Biomedical Technology, BRIS, R., MAJERNIK, J., PANCERZ, K., ZAITSEVA, E., Eds. Springer International Publishing, 2016, pp. 119-141. Go to original source...
    30. KVET, M., MATIASKO, K.: Column Level Uni-temporal Data, Communications - Scientific Letters of the University of Zilina, vol. 16, No. 1, pp. 97-104, 2014. Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content