The server disconnection problem on a ring network

In the server disconnection problem, a network with m servers and their users is given and an attacker is to destroy a set of edges to maximize his net gain defined as the total disconnected utilities of the users minus the total edge–destruction cost. The problem is known to be NP–hard. In this paper, we study the server disconnection problem restricted to a ring network. We present an efficient combinatorial algorithm that generates an optimal solution in polynomial time.