Building Reliability-Improving Network Transformations

摘要

A fundamental problem in network reliability analysis is to find the connectedness probability of a random graph subject to perfect nodes and independent link failures with identical probabilities. This connectedness probability is called the all-terminal reliability, and its determination is a challenging problem. In this paper we study the corresponding network design problem: which is the best way to connect q links among p nodes in order to maximize the all-terminal reliability? The optimal solutions to this problem are called uniformly most-reliable graphs. To the best of our knowledge, the literature offers a single reliability-improving network transformation called swing surgery, credited to Kelmans. Here, we offer two novel reliability-improving transformations which, even simple, they help to improve the reliability in a uniform sense (i.e., under all feasible link failure probability). Supported by the previous transformations, we prove that Yutsis graph is uniformly most-reliable, which is currently a computationally prohibitive problem. Conjectures and open problems are also discussed.