Network Resilience

The resilience of a network is a measure of its reliability; it is the expected number of node pairs which can communicate. The resilience of an n-vertex series-parallel network can be computed in $O(n^2 )$ time. The algorithm employs the recursive structure of maximal series-parallel networks. In contrast to this, computing the resilience of a planar network is shown to be #P-complete.