2014/09/26 by Eduardo Canale, Canale, Eduardo, Pablo Romero +3
Computer Science · Decision Sciences · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Concrete Corrosion and Durability #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Probabilistic and Robust Engineering Design #Reliability and Maintenance Optimization #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1409.7688
openalex publication_date 2014/09/26 · arxiv created 2014/10/01 · arxiv updated 2014/10/02 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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 nodes are perfect but links fail stochastically and independently, with probabilities qi=1-pi. The diameter-constrained reliability (DCR for short), is the probability that the terminals of the resulting subgraph remain connected by paths composed by d links, or less. This number is denoted by RK,Gd(p). The general computation of the parameter RK,Gd(p) belongs to the class of NP-Hard problems, since is subsumes the complexity that a random graph is connected. A discussion of the computational complexity for DCR-subproblems is provided in terms of the number of terminal nodes k=|K| and diameter d. Either when d=1 or when d=2 and k is fixed, the DCR is inside the class P of polynomial-time problems. The DCR turns NP-Hard even if k ≥ 2 and d≥ 3 are fixed, or in an all-terminal scenario when d=2. The traditional approach is to design either exponential exact algorithms or efficient solutions for particular graph classes. The contributions of this paper are two-fold. First, a new recursive class of graphs are shown to have efficient DCR computation. Second, we define a factorization method in order to develop an exact DCR computation in general. The approach is inspired in prior works related with the determination of irrelevant links and deletion-contraction formula.