Journal
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
Volume 53, Issue 3, Pages 649-680Publisher
SPRINGER
DOI: 10.1007/s10589-012-9458-y
Keywords
Critical node problem; Branch and cut; Valid inequalities; Reformulation-linearization technique
Ask authors/readers for more resources
In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can be solved in polynomial time. We derive different valid inequalities and some theoretical results about them. We also propose an alternative model based on a quadratic reformulation of the problem. Finally, we perform many computational experiments and analyze the corresponding results.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available