Search

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.

Let [ABSTRACT FROM AUTHOR]

We propose a polynomial-time algorithm for detecting and deleting classes of network edges which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may lead to important computational gains when combined with an exact method to calculate the reliability. For illustration, we integrate this algorithm within an exact recursive factorization approach based upon Moskowitz's edge decomposition. Experiments conducted on different real-world topologies confirmed a substantial computational gain, except when highly-dense graphs were tested. [ABSTRACT FROM PUBLISHER]

Abstract: Let be a digraph with a distinguished set of terminal vertices and a vertex . We define the -diameter of G as the maximum distance between s and any of the vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the diameter-constrained -terminal reliability of G, , is defined as the probability that surviving arcs span a subgraph whose -diameter does not exceed D. The diameter-constrained network reliability is a special case of coherent system models, where the domination invariant has played an important role, both theoretically and for developing algorithms for reliability computation. In this work, we completely characterize the domination of diameter-constrained network models, giving a simple rule for computing its value: if the digraph either has an irrelevant arc, includes a directed cycle or includes a dipath from s to a node in K longer than D, its domination is 0; otherwise, its domination is to the power . In particular this characterization yields the classical source-to-K-terminal reliability domination obtained by Satyanarayana. Based on these theoretical results, we present an algorithm for computing the reliability. [Copyright &y& Elsevier]