An Efficient Algorithm for Finding the k-edge Survivability in Ring Networks ∗
Young‐Soo Myung · Management Science and Financial Engineering · 2010
Given an undirected network with a set of source?sink pairs, we are assumed to get a benefit if a pair of source and sink nodes are connected. The k?edge survivability of a network is defined as the total benefit secured after arbitrarily selected k edges are destroyed. The problem of computing k?edge survivability is known to be NP?hard and has applications of evaluating the survivability or vulnerability of a network. In this paper, we consider the k?edge survivability problem restricted to ring networks and develop an algorithm to solve it in O(n³|K|) time where n is the number of nodes and K is the set of source?sink pairs.