کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141748 | 957088 | 2012 | 17 صفحه PDF | دانلود رایگان |
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 kk-hole subgraphs. We randomly generate a set of test instances, on which we demonstrate the computational efficacy of our approaches.
Journal: Discrete Optimization - Volume 9, Issue 3, August 2012, Pages 172–188