We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DIAMETER CONSTRAINED RELIABILITY OF LADDERS AND SPANISH FANS.
- Authors
CANCELA, Héctor; ROBLEDO, Franco; ROMERO, Pablo; SARTOR, Pablo
- Abstract
We are given a graph G = (V, E), terminal set K ⊆ V and diameter d > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short) is the probability that the K-diameter is not greater than d in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals k = |K| and diameter d. Here, we prove that if d > 2, the problem is NP-Hard when K = V, and second, we compute the DCR efficiently for ladders and Spanish fans.
- Subjects
GRAPH theory; PROBABILITY theory; COMPUTATIONAL complexity
- Publication
Yugoslav Journal of Operations Research, 2016, Vol 26, Issue 1, p17
- ISSN
0354-0243
- Publication type
Article
- DOI
10.2298/YJOR140721004C