A Novel Multistate Minimal Cut Vectors Problem and Its Algorithm

Network reliability is always a powerful index for measuring the performance of the multistate flow network (MFN) that is commonly used to model real-world applications. The multistate minimal cut (MC) vector is a special vector, and it is one of the most popular tools in evaluating the reliability of MFNs. Due to its importance, a novel multistate MC vectors problem is proposed by extending the traditional multistate MC vectors problem from a specific fixed flow to all different flows for more applications. To solve this novel problem, a new algorithm is proposed. The time complexity and demonstration of the proposed algorithm are analyzed, and examples are provided. An experiment is also conducted to compare the proposed multistate MC vectors algorithm and the multistate minimal path vectors algorithm (another important method of calculating MFN reliability).

I. Introduction

A multistate flow network (MFN) has many different arc states representing different performance levels, and it has many useful practical applications [3]–[12]. Numerous real-world multistate systems, e.g., the oil/gas production systems [3], power transmission and distribution systems [4], [5], transportation systems [6], grid and cloud computing [7], Internet of Things [8], wireless sensor network [9], etc. [10]–[14], have therefore been modeled by MFNs.