Path-Based and Cut-Based Recursive Decomposition Algorithms for Network Reliability Evaluation

Abstract eng:
In this paper, a path-based recursive decomposition algorithm (PRDA) and a cut-based recursive decomposition algorithm (CRDA) are introduced to evaluate the network reliability. Firstly, a structural function and a complementary structural function are established. The PRDA takes a shortest minimal path(MP) from the source to the sink as decomposition policy and constructs a recursive decomposition process. During the decomposition, the disjoint minimal paths (DMPs) and the disjoint minimal cuts (DMCs) are enumerated simultaneously. Therefore, a probabilistic inequality can be employed to give the results which satisfy a prescribed error bound. Similarly, the CRDA takes a minimal cut (MC) as decomposition policy. It also gives the DMPs and the DMCs simultaneously. A network with 17 nodes and 32 edges is studied to compare two algorithms. It is found that the PRDA is suitable to give the reliability of the network which owns high-reliability edges while the CRDA seems more suitable for the network which owns low-reliability edges. Two reasons, the contributions of the DMP and the DMC to network reliability are completely different when edges own different reliabilities, and the major goals of two algorithms are completely different, are presented to explain their different applicabilities.

• Export as: BibTeX | MARC | MARCXML | DC | EndNote | NLM | RefWorks
• Add to your basket