Full complexity analysis of the diameter-constrained reliability

Full complexity analysis of the diameter-constrained reliability

0.00 Avg rating0 Votes
Article ID: iaor201526606
Volume: 22
Issue: 5
Start Page Number: 811
End Page Number: 821
Publication Date: Sep 2015
Journal: International Transactions in Operational Research
Authors: , , , ,
Keywords: networks, design
Abstract:

Let G=(V,E) be a simple graph with |V|=n nodes and |E|=m links, a subset K⊆V of ‘terminals,’ a vector p=(p1,...,pm)∈[0,1]m, and a positive integer d, called ‘diameter.’ We assume that nodes are perfect but links fail stochastically and independently, with probabilities qi=1−pi. The ‘diameter‐constrained reliability’ (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of d links, or less. This number is denoted by RK,Gd(p). The general DCR computation belongs to the class of NP‐hard problems, since it subsumes the problem of computing the probability that a random graph is connected. The contributions of this paper are twofold. First, a full analysis of the computational complexity of DCR subproblems is presented in terms of the number of terminal nodes k=|K| and the diameter d. Second, we extend the class of graphs that accept efficient DCR computation. In this class, we include graphs with bounded co‐rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant to robust network design.

Reviews

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