Network Reliability: Approximation Algorithms

When a network is modeled by a graph and edges of the graph remain reliable with a given probability, the probability of the graph remaining connected is called the reliability of the network. This talk discusses several methods of approximation in calculating the reliability of the network, both when all edges are reliable with a single fixed probability, and when the probability is allowed to vary by edge. In the case where all edges have the same probability, there are two methods, one based on sequential importance sampling and the other based on Monte Carlo Markov chain. These two methods interact to form a single method of estimating the coefficients of the polynomial. In the case where the probabilities vary by edge, there are again two methods, both based on sequential importance sampling, each of which has its own strengths and weaknesses. One of these methods exploits the similarities that arise since reliability is a special case of the Tutte polynomial, while the other arises more directly from the method used on the single variable problem.

Speaker Bio: Dr. Elizabeth Moseman got her Ph.D. in mathematics from Dartmouth College under Dr. Peter Winkler. After 3 years of teaching at the United States Military Academy at West Point, she came to NIST as an NRC postdoctoral fellow to study applications of combinatorics, specifically in the area of probabalistic graph algorithms.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3668; at least 24 hours in advance.