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

Baichao Wu

Reliability Engineering and System Safety, 2025, vol. 262, issue C

Abstract: 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.

Keywords: Network reliability; Network decomposition; Multi-state flow network; D-minimal paths (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0951832025004211
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:reensy:v:262:y:2025:i:c:s0951832025004211

DOI: 10.1016/j.ress.2025.111220

Access Statistics for this article

Reliability Engineering and System Safety is currently edited by Carlos Guedes Soares

More articles in Reliability Engineering and System Safety from Elsevier
Bibliographic data for series maintained by Catherine Liu ().