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

Abstract

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.