New Method in Searching for All Minimal Paths for the Directed Acyclic Network Reliability Problem

The directed acyclic network (DAN) is a directed network without directed cycles and is always modeled various information, processes, and events or potential events of systems. Network reliability has been a popular tool to evaluate and validate the performance of DAN. In this study, a new simple algorithm is proposed to find all minimal paths to evaluate the DAN reliability. The proposed algorithm outperforms the existing known algorithms in calculating the DAN reliability from both theoretical and experimental aspects. The correctness and time complexity of the proposed algorithm are demonstrated and analyzed. The proposed algorithm is demonstrated on a benchmark DAN and tested its efficiency by applying it to another 20 randomly generated networks.

I. Introduction

Many systems, such as computer and communication systems, power transmission and distribution systems, transportation systems, and oil/gas production systems, can be modeled as networks in the planning, designing, and control of systems [1]–[10]. Network reliability is defined as a probability that networks function to meet our requirement, is one of the most important indices in evaluating and validating network performance, and plays an important role in our modern society [1]– [42]. For example, the (terminal pair) reliability of the acyclic (binary-state) network is the probability that both the source node and the sink node are connected by at least one path [11]–[15].