Johnson, Donald B.; Raab, Larry Complexity of network reliability and optimal resource placement problems. (English) Zbl 0813.68116 SIAM J. Comput. 23, No. 3, 510-519 (1994). Given a set of sits, communication links, rational reliability probabilities on both sites and links, and a distribution of access requests, find the optimal sit, where a site \(x\) is optimal if placing the resource at site \(x\) maximizes availability. In this paper, the authors proved that this problem is \(\# P\)-complete. Reviewer: Du Ding-Zhu (Minneapolis) Cited in 1 Document MSC: 68Q25 Analysis of algorithms and problem complexity 68P15 Database theory 68M15 Reliability, testing and fault tolerance of networks and computer systems Keywords:rational reliability probabilities PDF BibTeX XML Cite \textit{D. B. Johnson} and \textit{L. Raab}, SIAM J. Comput. 23, No. 3, 510--519 (1994; Zbl 0813.68116) Full Text: DOI