Diameter constrained reliability of ladders and Spanish fans
DOI:
https://doi.org/10.2298/YJOR140721004CKeywords:
diameter constrained reliability, computational complexity, graph theoryAbstract
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.References
Ball, M. O., Computational complexity of network reliability analysis: An overview, IEEE Transactions on Reliability, 35 (3) (1986) 230-239.
Ball, M.O., and Provan, J.S., “The complexity of counting cuts and of computing the probability that a graph is connected”, SIAM J. Computing, 12 (1983) 777-788.
Canale, E., Cancela, H., Robledo, F., Rubino, G. and Sartor, P., “On computing the 2-diameter-constrained K-reliability of networks”, International Transactions in Operational Research, 20 (1) (2013) 49-58.
Cancela, H., and Petingi, L., “Reliability of communication networks with delay constraints: computational complexity and complete topologies”, International Journal of Mathematics and Mathematical Sciences, 29 (2004) 1551-1562.
Colbourn, C.J., “Reliability issues in telecommunications network planning”. Chapter 9 in Sansó, B. and Soriano, P. (eds.) Telecommunications network planning, Kluwer Academic Publishers, London/Dordrecht/Boston (1999) 135-146.
Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP Completeness, W. H. Freeman and Company, New York, NY, USA (1979).
Migov, D., “Computing diameter constrained reliability of a network with junction points”, Automation and Remote Control, 72 (2011) 1415-1419.
Petingi, L., and Rodriguez, J., “Reliability of networks with delay constraints”, Congressus Numerantium, 152 (2001) 117-123.
Provan, S.J., and Ball, M.O., “The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected”, SIAM Journal on Computing, 12 (4) (2001) 777-788.
Rosenthal, A., “Computing the reliability of complex networks”, SIAM Journal on Applied Mathematics, 32 (2) (1977) 384-393.
Sartor, P., “Propriétés et méthodes de calcul de la fiabilité diamètre-bornée des réseaux”, PhD thesis, INRIA/IRISA, Université de Rennes I, Rennes, France (2013).
Valiant, L., “The complexity of enumeration and reliability problems”, SIAM Journal on Computing, 8 (3) (2009) 410-421.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
