Optimal Link Assignments for All-Terminal Network Reliability

Probabilistic networks whose links are subject to failure have been extensively studied in the literature. Their reliability is regarded as the network's ability to continue operation after failures have occurred. We consider the allterminal reliability measure, de ned as the probability that the network remains connected after failures. Previous work on this model assumes uniform failures probabilities for all links. In this paper, we discuss the design problem of assigning given distinct probabilities to the links of a network so as to maximize the reliability of the system. We determine optimal link assignments for some sparse networks such as multi-rings, and show that the problem is NP-hard in general