出版社:Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Economics Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mechanical Engineering, Belgrade
摘要:We are given a graph G = (V, E), terminal set K V and diameter d > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short), is the probability that the K-diameter is not greater than d in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals k = jKj and diameter d. Here, we prove that when d > 2 the problem is NP-Hard when K = V. Second, we compute the DCR efficiently for Ladders and Spanish Fans. Open problems and trends for future work are discussed in the conclusions.
关键词:diameter constrained reliability; computational complexity; graph theory