Reliability evaluation is a useful tool for network performance demonstration, and therefore has become an increasingly relevant task in network design and operation. The multistate minimal cut (called d-MC for short) method is a popular algorithm for reliability evaluation of multistate flow networks. This article focuses on d-MC problem, and presents some new results to improve its solution. Grounded on the newly obtained results, an algorithm is proposed to find d-MCs, together with discussions on its time complexity that compares favorably with the existing methods. An illustration of the presented algorithm is provided by solving a simple example. Furthermore, numerical experiments and a case study are conducted to demonstrate the advantage and the utility of the proposed algorithm, respectively.
Multistate flow networks (MFNs) and their reliability problem have been studied extensively. However, most of the research on MFN reliability assumes that flow into and out of any arc is equal. In practical applications, flow may experience loss during transmission such that flow into and out of an arc may not be equal. Thus, this article concentrates on the reliability of an MFN with flow loss effect, defined as the probability that the sink node can receive a flow of at least d units when the flow experiences loss without replenishment during transmission. Using minimal paths, a simple method is put forth to compute this reliability index, and the solution procedure is illustrated via a simple network example. Finally, computational experiments are provided to investigate the impact of flow loss on network reliability.
2 July 2024 in Reliability Engineering & System Safety
k-terminal network reliability is the probability that k terminal vertices are connected given that edges in the network fail independently while vertices do not fail. It depends on the distribution of these terminal vertices as well as network topology. The problem of computing k-terminal reliability is NP-hard. Previous literature mainly focus on designing efficient algorithms to compute it in different graphs, but are lacking in the analysis for optimal distribution of k terminal vertices in sparse graphs, within which those with n nodes and m edges, where m ≤ n + 1, are most basic classes. Hence, it is of great significance to investigate the optimal distribution of terminal vertices in these classes of graphs before considering general cases. In this paper, we prove that k-terminal network reliability obtains the maximum if k terminal vertices induce a connected subgraph. Further, we give equations of maximum reliability for all possible graphs in the above classes. The experiments illlustrate the variation, with several parameters and according to our theoretical results, of maximal k-terminal reliability, and provide observations for graphs with any number of edges.