An algorithm for the graph disconnection problem

An algorithm for the graph disconnection problem

0.00 Avg rating0 Votes
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: ,
Keywords: graphs, networks
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.