Full complexity analysis of the diameter-constrained reliability
| Autor: | Franco Robledo, Pablo Sartor, Pablo Romero, Eduardo Canale, Héctor Cancela |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Random graph
Discrete mathematics Computational complexity theory Strategy and Management Management Science and Operations Research Computer Science Applications Planar graph Modular decomposition Combinatorics Indifference graph symbols.namesake Pathwidth Chordal graph Management of Technology and Innovation Bounded function symbols Business and International Management MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | International Transactions in Operational Research. 22:811-821 |
| ISSN: | 0969-6016 |
| DOI: | 10.1111/itor.12159 |
| Popis: | Let be a simple graph with nodes and links, a subset of “terminals,” a vector , and a positive integer d, called “diameter.” We assume that nodes are perfect but links fail stochastically and independently, with probabilities . 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 . The general DCR computation belongs to the class of -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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|