Reliability of communication networks with delay constraints: computational complexity and complete topologies
type: Item
instance of: scholarly article
title: Reliability of communication networks with delay constraints: computational complexity and complete topologies
zbMATH Open document ID: 1061.05091
DOI: 10.1155/S016117120430623X
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2005-05-18T00:00:00Z
full work available at URL: https://eudml.org/doc/51252
review text: Summary: Let \(G=(V,E)\) be a graph with a distinguished set of terminal vertices \(K \subseteq 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 \geq 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 90B25
zbMATH DE Number: 2168706
zbMATH Keywords: distance
author: Héctor Cancela
author: L. Petingi
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2168706