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 -