文献类型：期刊文献

英文题名：A practical bounding algorithm for computing two-terminal reliability based on decomposition technique

作者：Niu, Yi-Feng[1,2]; Shao, Fang-Ming[2]

机构：[1] College of Mathematics and Information Science, Henan Polytechnic University, Henan Prov., 454000, China; [2] Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2011

卷号：61

期号：8

起止页码：2241

外文期刊名：Computers and Mathematics with Applications

收录：EI(收录号：20111513904405)

语种：英文

摘要：Two-terminal reliability, which is defined as the probability that there exists at least one path from source node to sink node, is an important performance measure in network system. However, it is well known that the complexity of exact two-terminal reliability evaluation is NP-hard. This paper considers a bounding algorithm for computing two-terminal reliability based on decomposition technique originally used in computing multi-state reliability. Compared with traditional bounding algorithms, the proposed algorithm requires neither all MPs/MCs to be enumerated in advance, nor all arcs to have the same state probabilities. It can sequentially improve the quality of approximation according to a predetermined value Ε. Especially, it may be an exact algorithm if it runs into completion. An example shows that the proposed algorithm is practical and effective. ? 2010 Elsevier Ltd. All rights reserved.