TY - JOUR
T1 - Exact interdiction models and algorithms for disconnecting networks via node deletions
AU - Shen, Siqian
AU - Smith, J. Cole
AU - Goli, Roshan
N1 - Funding Information:
The authors are grateful to the comments of three referees and an associate editor, whose remarks led to an improved contribution and presentation. Dr. Smith gratefully acknowledges the support of the Defense Threat Reduction Agency under Grant HDTRA1-10-1-0050 and the National Science Foundation under Grant CMMI-1100765 .
PY - 2012/8
Y1 - 2012/8
N2 - 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.
AB - 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.
KW - Mixed-integer programming
KW - Network interdiction
KW - Valid inequalities
UR - http://www.scopus.com/inward/record.url?scp=84865137944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865137944&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2012.07.001
DO - 10.1016/j.disopt.2012.07.001
M3 - Article
AN - SCOPUS:84865137944
SN - 1572-5286
VL - 9
SP - 172
EP - 188
JO - Discrete Optimization
JF - Discrete Optimization
IS - 3
ER -