Resilience of partial k ‐tree networks with edge and node failures
Erick Mata‐Montero · Networks · 1991
Abstract The resilience of a network is the expected number of pairs of nodes that can communicate. Computing the resilience of a network is a #P‐complete problem even for planar networks with fail‐safe nodes. We generalize an O ( n 2 ) time algorithm to compute the resilience of n ‐node k ‐tree networks with fail‐safe nodes to obtain an O(n) time algorithm that computes the resilience of n ‐node partial k ‐tree networks with edge and node failures (given a fixed k and an embedding of the partial k ‐tree in a k ‐tree).