期刊
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
卷 53, 期 3, 页码 649-680出版社
SPRINGER
DOI: 10.1007/s10589-012-9458-y
关键词
Critical node problem; Branch and cut; Valid inequalities; Reformulation-linearization technique
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据