A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that in an undirected graph, assuming each edge fails independently, the remainder of the graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and …