Reliability serves as a fundamental indicator for evaluating the performance of multi-state flow networks (MFNs).d-minimal cuts (d-MCs) are recognized as one of the most efficient tools for MFN reliability assessment. Findingd-MCs for all possible d plays a vital role in capturing the whole picture of MFN reliability. The existing method is grounded on the addition of (d−1)-MCs and a unit vector to generate d-MCs for all possibled. In contrast, this article proposes a novel method based on the subtraction of (d+1) MCs and a unit vector to obtaind-MCs for all possible d with enhanced computational performance. To date, this study is the first to explore the subtraction-based method for thedMCs for all possibledproblem. Numerical experiments confirm that the proposed subtraction-based method is more efficient in comparison with the well-known addition-based method.

Multi-state flow network (MFN) reliability problem has attracted considerable interest in the past decades. MFN reliability subject to flow loss, defined as the probability that the demand at the destination can be met when flow undergoes loss during transmission, is an extension of the conventional MFN reliability problem. The current studies on MFN reliability subject to flow loss have been carried out under the assumption that flow and demand are integers, which means the existing algorithms are unavailable to the network with non-integer demand. Moreover, the existing algorithms would yield underestimated reliability values even if the demand is an integer, which limits their practical applications. This article goes one step forward to address the general case where flow and demand can be integers or non-integers, and presents an efficient direct algorithm to accurately compute MFN reliability subject to flow loss. The reported algorithm is not only available to more complex scenarios with non-integer flow and demand, but also indicates a performance advantage. Furthermore, a case study is analyzed to highlight the practical relevance of the algorithm.

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 leastdunits 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.

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 illustrate 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.

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.