Diameter constrained reliability: Complexity, distinguished topologies and asymptotic behavior

Diameter constrained reliability: Complexity, distinguished topologies and asymptotic behavior

0.00 Avg rating0 Votes
Article ID: iaor2016211
Volume: 66
Issue: 4
Start Page Number: 296
End Page Number: 305
Publication Date: Dec 2015
Journal: Networks
Authors: , , , ,
Keywords: design, decision, behaviour, graphs, stochastic processes, quality & reliability
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 = ( p 1 , … , p m ) ∈ [ 0 , 1 ] m and a positive integer d , called the diameter. We assume vertices are perfect but edges fail stochastically and independently, with probabilities q e = 1 − p e . 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 R K , G d ( p ) . The general DCR computation problem belongs to the class of N P ‐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 N P ‐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 N P ‐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.

Reviews

Required fields are marked *. Your email address will not be published.