Skip to Main content Skip to Navigation
Conference papers

Network utility problem and easy reliability polynomials

Abstract : We model a communication system by a network, were the terminals are perfect but links may fail randomly, with identical probability q = 1 - p. This defines a partial random network. The all-terminal reliability R(p) is the probability that this random graph is connected, and it is a polynomial in p. Finding the reliability polynomial can be reduced to a hard counting problem. The contributions of this paper are two-fold. First, we fully determine all subgraphs that accept an easy counting technique, and as a consequence, the reliability polynomial is directly retrieved. More specifically, we define the “level of difficulty” of a graph, and find the reliability polynomials of all graphs with non-positive level of difficulty. The second contribution is to propose a fundamental problem from survivable network design, called the Network Utility Problem. The goal is to maximize the network utility, under a minimum edge-connectivity requirement. The network utility is defined as the opposite of the level of difficulty minus one, and it is never greater than unity. The upper-bound is achieved only in trees and cycles. We prove that Harary graphs achieve the optimal value for the Network Utility Problem. Finally, we present open problems that provide hints for future work.
Document type :
Conference papers
Complete list of metadata
Contributor : Yassine Hadjadj Aoul <>
Submitted on : Friday, December 30, 2016 - 1:16:29 PM
Last modification on : Friday, January 8, 2021 - 3:12:38 AM



Eduardo Canale, Pablo Romero, Gerardo Rubino, Warnes Xavier. Network utility problem and easy reliability polynomials. RNDM 2016 - 8th International Workshop on Resilient Networks Design and Modeling, Sep 2016, Halmstad, Sweden. ⟨10.1109/RNDM.2016.7608271⟩. ⟨hal-01423584⟩



Record views