We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Diameter Constrained Reliability: Complexity, Distinguished Topologies and Asymptotic Behavior.
- Authors
Canale, Eduardo; Cancela, Héctor; Robledo, Franco; Romero, Pablo; Sartor, Pablo
- Abstract
Let G = (V, E) be a simple graph with |V| = n vertices and |E| = m edges, a subset K ⊆ V of terminals, a vector p = (p1, ..., pm) ∈ [0, 1]m and a positive integer d, called the diameter. We assume vertices are perfect but edges fail stochastically and independently, with probabilities qe = 1 - pe. The diameter constrained reliability (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of d or fewer edges. This number is denoted by RdK,G(p). The general DCR computation problem belongs to the class of NP-hard problems. The contributions of this article are threefold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminal vertices k =|K| and the diameter d. Either when d = 1 or when d = 2 and k is fixed, the DCR problem belongs to the class P of polynomial-time solvable problems. The DCR problem becomes NP-hard when k ≥ 2 is a fixed input parameter and d ≥ 3. The cases where k = n or k is a free input parameter and d ≥ 2 is fixed have not been studied in the prior literature. Here, the NP-hardness of both cases is established. Second, we categorize certain classes of graphs that allow the DCR computation to be performed in polynomial time. We include graphs with bounded corank, graphs with bounded genus, planar graphs, and in particular, Monma graphs, which are relevant in robust network design. Third, we introduce the problem of analyzing the asymptotic properties of the DCR measure in networks that grow infinitely following given probabilistic rules. We introduce basic results for Gilbert's random graph model.
- Subjects
RELIABILITY of telecommunication; COMPUTATIONAL complexity; RANDOM graphs
- Publication
Networks, 2015, Vol 66, Issue 4, p296
- ISSN
0028-3045
- Publication type
Article
- DOI
10.1002/net.21654