文献类型：期刊文献

英文题名：A Diameter-Constrained Approximation Algorithm of Multistate Two-Terminal Reliability

作者：Zhang, Zuyuan[1];Shao, Fangming[2]

机构：[1]Arizona State Univ, Sch Elect Comp & Energy Engn, Tempe, AZ 85281 USA;[2]East China Univ Sci & Technol, Sch Sci, Shanghai 200237, Peoples R China

年份：2018

卷号：67

期号：3

起止页码：1249

外文期刊名：IEEE TRANSACTIONS ON RELIABILITY

收录：;EI(收录号：20182205264423);WOS:【SCI-EXPANDED(收录号:WOS:000443970200035)】；

语种：英文

外文关键词：Lower bound; multistate flow network; two-terminal reliability

摘要：Multistate two-terminal reliability is the probability that d units of flow can be transmitted from the source node s to the sink node t. It is an important index for a flow network, and its value is based on minpaths or mincuts. However, the enumeration of all minpaths is not feasible in large networks. Hence, designing an approximation algorithm is valuable for the reliability ofmultistate flow networks. In this paper, we model a multistate flow network as an acyclic directed graph and find that the contribution of minpaths to the reliability changes with their lengths, so we consider the approximation solution of multistate two-terminal reliability by constraining diameter of the network. Furthermore, we give a sufficient and necessary condition to detect irrelevant arcs and propose an approximation algorithm by controlling the value of diameter constraint. In the meantime, the reliability with diameter constraint is also a parameter to partially reflect the performance of network. The experiments demonstrate the effectiveness and efficiency of the algorithm.