Article ID: | iaor20063641 |
Country: | South Korea |
Volume: | 11 |
Issue: | 1 |
Start Page Number: | 49 |
End Page Number: | 61 |
Publication Date: | May 2005 |
Journal: | International Journal of Management Science |
Authors: | Kim Hyun-Joon, Myung Young-Soo |
Keywords: | graphs, networks |
We consider the graph disconnection problem, which is to find a set of edges such that the total cost of destroying the edges is no more than a given budget and the weight of nodes disconnected from a designated source by destroying the edges is maximized. The problem is known to be NP-hard. We present an integer programming formulation for the problem and develop an algorithm that includes a preprocessing procedure for reducing the problem size, a heuristic for providing a lower bound, and a cutting plane algorithm for obtaining an upper bound. Computational results for evaluating the performance of the proposed algorithm are also presented.