文献类型：会议论文

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

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

机构：[1]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[2]Henan Polytech Univ, Coll Math & Informat Sci, Jiaozuo 454000, Henan Prov, Peoples R China

会议论文集：3rd International Symposium on Nonlinear Dynamics

会议日期：SEP 25-28, 2010

会议地点：Shanghai, PEOPLES R CHINA

语种：英文

外文关键词：Two-terminal reliability; Decomposition technique; MP/MC

摘要：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 E. Especially, it may be an exact algorithm if it runs into completion. An example shows that the proposed algorithm is practical and effective. (C) 2010 Elsevier Ltd. All rights reserved.