An Innovative and Very Efficient Algorithm for Searching All Multistate Minimal Cuts Without Duplicates
Paweł Marcin Kozyra
Abstract
Many real-world systems can be modeled by limited-flow multistate networks composed of multistate components. Reliability evaluation of multistate flow networks features in designing and control of these systems. The multistate minimal cut (called <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -MC for short) method is a popular one for evaluating network reliability. This article is devoted to the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -MC problem. It presents new results being the base of an algorithm finding <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$d$</tex-math></inline-formula> -MC candidates without duplicates and verifying them more efficiently and more quickly than existing algorithms. Discussion on the time complexity of this algorithm and an example of its use are provided. Finally, numerical experiments are conducted to demonstrate the advantage of the algorithm under discussion over other algorithms.