Near-Linear Estimation of Network UnreliabilityResearch Paper
The unreliability of a network is the probability that it becomes disconnected when its links fail at random. It is the basic reliability measure for communication and transport networks, and computing it exactly is #P-hard (Provan–Ball 1983). Approximation is therefore the only option. A Monte Carlo sample has relative variance , which is…