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

H. Cancela and L. Petingi

International Journal of Mathematics and Mathematical Sciences, 2004, vol. 2004, 1-12

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 , R K ( 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 R K ( G , D ) is NP-hard, as this measure subsumes the classical K -terminal reliability R K ( 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.

Date: 2004
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2004/314763.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2004/314763.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:314763

DOI: 10.1155/S016117120430623X

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().