Exact interdiction models and algorithms for disconnecting networks via node deletions
Exact interdiction models and algorithms for disconnecting networks via node deletions
复制标题
DOI：
10.1016/j.disopt.2012.07.001
复制
发表时间：
2012-08-01
影响因子：
1.1
通讯作者：
Goli, Roshan
中科院分区：
文献类型：
--
作者：
Shen, Siqian;Smith, J. Cole;Goli, Roshan
本文分析了通过删除节点子集来最大化无向图的不连通性的问题。我们考虑衡量图连接性的三个指标：连接组件的数量（我们试图最大化）、最大组件大小（我们尝试最小化）以及删除节点后重新连接图所需的最小成本（我们尝试最大化）。我们将每个问题表述为一个混合整数程序，然后通过检查 k 孔子图的中间动态规划解来研究前两个连通性目标的有效不等式。我们随机生成一组测试实例，在这些实例上我们展示了我们方法的计算效率。由 Elsevier B.V. 出版
This paper analyzes the problem of maximizing the disconnectivity of undirected graphs by deleting a subset of their nodes. We consider three metrics that measure the connectivity of a graph: the number of connected components (which we attempt to maximize), the largest component size (which we attempt to minimize), and the minimum cost required to reconnect the graph after the nodes are deleted (which we attempt to maximize). We formulate each problem as a mixed-integer program, and then study valid inequalities for the first two connectivity objectives by examining intermediate dynamic programming solutions to k-hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches. Published by Elsevier B.V.