Journal
DISCRETE OPTIMIZATION
Volume 9, Issue 3, Pages 172-188Publisher
ELSEVIER
DOI: 10.1016/j.disopt.2012.07.001
Keywords
Network interdiction; Mixed-integer programming; Valid inequalities
Funding
- Defense Threat Reduction Agency [HDTRA1-10-1-0050]
- National Science Foundation [CMMI-1100765]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1100765] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
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