Título:
Diameter-constrained reliability : Complexity, factorization and exact computation in weak graphs.
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Canale, Eduardo
Piccini, Juan
Robledo, Franco
Romero, Pablo
Piccini, Juan
Robledo, Franco
Romero, Pablo
Tutor:
Tipo de documento:
Preprint
Editor:
Palabras clave:
Computational Complexity
Network Reliability
Diameter-Constrained Reliability
Network Reliability
Diameter-Constrained Reliability
Descriptores:
Año de publicación:
2014
Contenido:
Resumen:
In this paper we address a problem from the field of network reliability, called diameter-constrained reliability. Specifically, we are given a simple graph G = (V, E) 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 RdK,G(p).
The general DCR computation is inside the class of NP-Hard problems, since is subsumes the complexity that a random graph is connected. In this paper the computational complexity of DCR-subproblems is discussed in terms of the number of terminal nodes k = [K] and diameter d. A factorization formula for exact DCR computation is provided, that runs in exponential time in the worst case. Finally, a revision of graph-classes that accept DCR computation in polynomial time is then included. In this class we have graphs with bounded co-rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant in robust network design. We extend this class adding arborescence graphs. A discussion of trends for future work is offered in the conclusions.
Descripción:
metadata.articulos.dc.description.uri:
Editorial:
EN:
Financiadores:
Citación:
Canale, E., Piccini, J., Robledo, F, y otros. Diameter-constrained reliability : Complexity, factorization and exact computation in weak graphs [Preprint]. Publicado en: LANC '14 : Latin America Networking Conference, Montevideo, Uruguay, 18-19 sep. 2014, pp. 1-7.
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Grupo de investigación:
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| CPRR14.pdf | Preprint | 240.39 KB | Adobe PDF |