Computing Reliability Polynomials
Mike Monagan, CECM, SFU
Abstract: The reliability polynomial R(G,p) of a network G is a polynomial in p that is the probability that the network G remains connected when each edge in G may "fail" with probability p. It is thus a theoretical measure of the reliability of the network. The reliability polynomial is related to the Tutte polynomial from graph theory. Like the Tutte polynomial, it is one of many graph theoretic polynomials, such as the chromatic polynomial, which are known to be NP-hard to compute. In this talk I will first present the method based on edge deletion and edge contraction for computing the reliablity polynomial. I will then present some Graph decompositions which facilitate the computation of R(G,p) and the connection with the Tutte polynomial. I will present our implementation of this method in Maple, and compare it with Jeff Farr's Maple 12 implementation in the GraphTheory package.