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 multistateMC 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).