Article ID: | iaor20124610 |
Volume: | 9 |
Issue: | 3 |
Start Page Number: | 172 |
End Page Number: | 188 |
Publication Date: | Aug 2012 |
Journal: | Discrete Optimization |
Authors: | Smith J Cole, Shen Siqian, Goli Roshan |
Keywords: | combinatorial optimization, programming: multiple criteria, programming: integer, graphs |
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