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
paper · pdf · doi:10.48550/arxiv.1409.7688
openalex publication_date 2014/09/26 · 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\nsubset K \⊆ V of \terminals, a vector p=(p1,...,pm) \∈\n[0,1]m and a positive integer d, called \diameter. We assume nodes\nare perfect but links fail stochastically and independently, with probabilities\nqi=1-pi. The \diameter-constrained reliability (DCR for short), is\nthe probability that the terminals of the resulting subgraph remain connected\nby paths composed by d links, or less. This number is denoted by\nRK,Gd(p). The general computation of the parameter RK,Gd(p)\nbelongs to the class of \N\P-Hard problems, since is\nsubsumes the complexity that a random graph is connected.\n A discussion of the computational complexity for DCR-subproblems is provided\nin terms of the number of terminal nodes k=|K| and diameter d. Either when\nd=1 or when d=2 and k is fixed, the DCR is inside the class \P\nof polynomial-time problems. The DCR turns \N\P-Hard even\nif k \≥ 2 and d\≥ 3 are fixed, or in an all-terminal scenario when\nd=2. The traditional approach is to design either exponential exact\nalgorithms or efficient solutions for particular graph classes.\n The contributions of this paper are two-fold. First, a new recursive class of\ngraphs are shown to have efficient DCR computation. Second, we define a\nfactorization method in order to develop an exact DCR computation in general.\nThe approach is inspired in prior works related with the determination of\nirrelevant links and deletion-contraction formula.\n