International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 29, Pages 1551-1562
doi:10.1155/S016117120430623X
Reliability of communication networks with delay constraints: computational complexity and complete topologies
1Instituto de Computación, Facultad de Ingeniería, Universidad de la República, J. Herrera y Reissig 565, Montevideo 11300, Uruguay
2Computer Science Department, College of Staten Island, City University of New York, 2800 Victory Boulevard, Staten Island, 10314, NY, USA
Received 22 June 2003
Copyright © 2004 H. Cancela and L. Petingi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Let G=(V,E) be a graph with a distinguished set of terminal
vertices K⫅V. We define the K-diameter of G as
the maximum distance between any pair of vertices of K. If the
edges fail randomly and independently with known probabilities
(vertices are always operational), the
diameter-constrained K-terminal reliability of G,
RK(G,D), is defined as the probability that surviving edges
span a subgraph whose K-diameter does not exceed D. In general, the computational complexity
of evaluating RK(G,D) is NP-hard, as this measure subsumes the
classical K-terminal reliability RK(G), known to belong to
this complexity class. In this note, we show that even though for
two terminal vertices s and t
and D=2, R{s,t}(G,D)
can be determined in polynomial time, the problem of calculating
R{s,t}(G,D) for fixed values of D, D≥3, is
NP-hard. We also generalize this result for any fixed number of
terminal vertices. Although it is very unlikely that general
efficient algorithms exist, we present a recursive formulation
for the calculation of R{s,t}(G,D) that yields a
polynomial time evaluation algorithm in the case of complete
topologies where the edge set can be partitioned into at most
four equi-reliable classes.