.png){kind=icon}
.png){kind=icon}
Return
Reliability Analysis for Disjoint Paths
.png){kind=icon}
PRE
AI
DOI：10.1109/TR.2018.2877775.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Our contemporary society survives on the services provided by several network infrastructures, such as communication, power, and transportation, so their reliability should be accurately evaluated from various aspects. While past studies defined network reliability in terms of connectivity, some of the network connections that have been established may suffer from insufficient resources, i.e., vertices may be connected on a network but flows might fail due to resource contention. As a first step to address resource protection, this paper introduces path disjointness to the field of network reliability analysis, i.e., we evaluate the probability that given terminals are connected via edge-or vertex-disjoint paths. In addition, we also deal with identifying critical links under path disjointness. Since network reliability analysis is a computationally tough problem, we propose efficient algorithms utilizing the data structure of binary decision diagrams. Numerical experiments show that our method scales up to a network with 189 links. We show that network reliability and the criticality of links are greatly dependent on path disjointness; this validates the importance of the proposed method.
Keywords:
Binary decision diagrams (BDDs)
disjoint paths
dynamic programming
network reliability
network theory
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
Organization
No organization information available