An improved algorithm for solving all <Emphasis Type="Italic">d</Emphasis>-MPs in multi-state networks |
| |
Authors: | Yifeng Niu Ziyou Gao Huijun Sun |
| |
Institution: | 1.School of Mathematics and Information Science,Henan Polytechnic University,Jiaozuo,China;2.School of Traffic and Transportation,Beijing Jiaotong University,Beijing,China |
| |
Abstract: | Reliability is a desirable performance indicator of many real-world systems to measure the quality level. One general method for evaluating multi-state reliability is using d-minimal paths (d-MPs). However, being an NP-hard problem, searching for all d-MPs is a rather challenging task. This paper proposes an improved algorithm to solve the d-MP problem. To reduce the search space of d-MPs, a concept of lower capacity bound is introduced into the d-MP problem, and an effective technique is developed to find lower capacity bounds. Meanwhile, the fast enumeration method which is a recent improvement to the traditional enumeration method is employed to solve d-MPs. In addition, by introducing the operation of transforming undirected edges into directed edges, the proposed algorithm is applicable to solving both directed networks and undirected networks. Through numerical experiments, it is found that the proposed algorithm holds a distinct advantage over the existing methods in solving all d-MPs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|