A novel d-flow network decomposition algorithm for fast search and efficient storage of all d-MPs

The d-MPs algorithm is one of the main algorithms for calculating the reliability of multi-state flow networks (MFNs). However, two issues remain unresolved in existing algorithms searching for d-MPs: redundant calculations during network decomposition and efficient storage of all d-MPs. A novel d-flow network decomposition algorithm is proposed to resolve the abovementioned issues. During the process of network decomposition with the demand d, the storage and identification of isomorphic subgraphs are utilized to avoid redundant decomposition of the subgraphs. Additionally, all d-MPs are stored in a directed graph, and finally, the depth-first search (DFS) algorithm is employed to search for all d-MPs. Furthermore, the proposed algorithm's time and space complexity is analyzed. Experimental results on the selected networks with different scenarios show that the efficiency of the proposed algorithm is significantly higher than the previous efficient methods in most cases. In Example 2, when d = 13, the proposed algorithm outperforms the previous fastest algorithm by 3.4 times. Additionally, Example 3 demonstrates that over 5.4 × 10⠶ valid d-MPs can be stored in a directed graph with only 819 vertices and 1572 edges, indicating the proposed method substantially reduces memory usage.1.The network is connected and free of self-loops;2.The capacity of each edge is a non-negative integer following a given probability distribution;3.The capacities of different edges are statistically independent.4.The vertex is perfectly reliable.5.The flow conservation law is obeyed.