International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 29, Pages 1551-1562

Reliability of communication networks with delay constraints: computational complexity and complete topologies

H. Cancela1 and L. Petingi2

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.


Let G=(V,E) be a graph with a distinguished set of terminal vertices KV. 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, D3, 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.