A revised layered-network algorithm to search for all d-minpaths of a limited-flow acyclic network

Many real-world systems are multistate and composed of multistate components in which the reliability can be computed in terms of the lower bound points of level d, called d-minpaths (d-MP). Such systems (electric power, transportation, etc.) may be regarded as flow networks whose arcs have statistically independent, discrete, limited and multivalued random capacities. This study focuses on how to find the entire path of d-MP before calculating the reliability of an acyclic network. Analysis of the authors' "revised layered network algorithm" (RLNA) and comparison to existing algorithms show that RLNA has the advantages: (1) it can be used to search for all MP, an NP-hard problem that is assumed to be known in advance in the existing algorithms; (2) the original NP-hard problem can be decomposed into several smaller subproblems using the RLNA such that the d-MP candidates are simple to find and verify, which is more effective than the existing methods; and (3) RLNA is easier to understand and implement. This paper first develops the intuitive RLNA. The computational complexity of RLNA is then analyzed and compared with existing methods. An example illustrates how all d-MP are generated.