.png){kind=icon}
.png){kind=icon}
Return
Universal Reliability Bounds for Sparse Networks
.png){kind=icon}
OA
AI
DOI：10.1109/TR.2021.3061075.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Consider a graph with perfect nodes and edges subject to independent random failures with identical probability. The all-terminal reliability is the probability that the resulting subgraph is connected. First, we fully characterize uniformly least reliable graphs (ULRG) whose co-rank is not greater than four. Universal reliability bounds are here introduced for those graphs. It is formally proved that ULRG is invariant under bridge-contractions, and maximize the number of bridges among all connected simple graphs with a prescribed number of nodes and edges. A closed-form for the maximum number of bridges is also given, which has an intrinsic interest from a graph-theoretic point of view. Finally, the cost-reliability tradeoff is discussed, comparing the number of edges required to reduce the reliability gaps between the least and most reliable graphs. A remarkable conclusion is that the network design is critical under rare event failures, where the reliability-gap between least and most-reliable networks is monotonically increasing with the number of terminals.
Keywords:
Reliability
Reliability theory
Bridges
Reliability engineering
Graph theory
Tools
Terminology
All-terminal reliability (ATR)
reliability bounds
uniformly least reliable graphs (ULRG)
uniformly most reliable graphs (UMRG)
Journal
IF:
5.7
Papers:
2.7K
Citations:
8.5K