
doi: 10.1002/net.21780
In classical network reliability, the system under study is a network with perfect nodes and imperfect links that fail randomly and independently. The probability that a given subset of terminal nodes belongs to the same connected component is called classical or ‐Terminal reliability. Although (and because) the classical reliability computation belongs to the class of ‐Hard problems, the literature offers many methods for this purpose, given the importance of the models. This article deals with diameter‐constrained reliability, where terminal nodes are further required to be connected by hops or fewer ( is a given strictly positive parameter of the metric called its diameter). This metric was defined in 2001, inspired by delay‐sensitive applications in telecommunications. Factorization theory is fundamental for the classical network reliability evaluation, and today it is a mature area. However, its extension to the diameter‐constrained context requires at least the recognition of irrelevant links, which is an open problem. In this article, irrelevant links are efficiently determined in the most used case, where , thus providing a first step toward a Factorization theory in diameter‐constrained reliability. We also analyze the metric in series‐parallel and composition graphs. The article closes with a Factoring algorithm and a discussion of trends for future work. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 283–291 2017
Computational Complexity, Diameter-constrained, computational complexity, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Network reliability, Series-Parallel Graphs, series-parallel graphs, Reliability, diameter-constrained reliability, composition graphs, Reliability, availability, maintenance, inspection in operations research, [INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF], Deterministic network models in operations research, network reliability, Theory, Composition Graphs, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, Factorization, factorization theory
Computational Complexity, Diameter-constrained, computational complexity, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Network reliability, Series-Parallel Graphs, series-parallel graphs, Reliability, diameter-constrained reliability, composition graphs, Reliability, availability, maintenance, inspection in operations research, [INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF], Deterministic network models in operations research, network reliability, Theory, Composition Graphs, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, Factorization, factorization theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
