.png){kind=icon}
.png){kind=icon}
Return
A Diameter-Constrained Approximation Algorithm of Multistate Two-Terminal Reliability
.png){kind=icon}
PRE
AI
DOI：10.1109/TR.2018.2829081.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Lower bound
multistate flow network
two-terminal reliability
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
5.7
Papers:
2.7K
Citations:
8.5K