Exact interdiction models and algorithms for disconnecting networks via node deletions

2006 Borgatti, 2006, Identifying sets of key players in a social network, Computational & Mathematical Organization Theory, 12, 21, 10.1007/s10588-006-7084-x Brown, 2006, Defending critical infrastructure, Interfaces, 36, 530, 10.1287/inte.1060.0252 Zhou, 2006, Epidemic dynamics on complex networks, Progress in Natural Science, 16, 452, 10.1080/10020070612330019 Alderson, 2008, Catching the “network science” bug: insight and opportunity for the operations researcher, Operations Research, 56, 1047, 10.1287/opre.1080.0606 Watts, 1998, Collective dynamics of ‘small-world’ networks, Nature, 393, 440, 10.1038/30918 Albert, 2000, Error and attack tolerance of complex networks, Nature, 406, 378, 10.1038/35019019 Tu, 2000, How robust is the Internet?, Nature, 406, 353, 10.1038/35019222 Arulselvan, 2009, Detecting critical nodes in sparse graphs, Computers and Operations Research, 36, 2193, 10.1016/j.cor.2008.08.016 Dinh, 2010, On approximation of new optimization methods for assessing network vulnerability, 1 Matisziw, 2009, Exploring the vulnerability of network infrastructure to disruption, The Annals of Regional Science, 43, 307, 10.1007/s00168-008-0235-x Murray, 2008, A methodological overview of network vulnerability analysis, Growth and Change, 39, 573, 10.1111/j.1468-2257.2008.00447.x Arroyo, 2010, Bilevel programming applied to power system vulnerability analysis under multiple contingencies, IET Generation, Transmission and Distribution, 4, 178, 10.1049/iet-gtd.2009.0098 Cormican, 1998, Stochastic network interdiction, Operations Research, 46, 184, 10.1287/opre.46.2.184 Lim, 2007, Algorithms for discrete and continuous multicommodity flow network interdiction problems, IIE Transactions, 39, 15, 10.1080/07408170600729192 P.A. San Martin, Tri-level optimization models to defend critical infrastructure, Master’s Thesis, Naval Postgraduate School, Monterey, CA, September 2007. Smith, 2007, Survivable network design under optimal and heuristic interdiction scenarios, Journal of Global Optimization, 38, 181, 10.1007/s10898-006-9067-3 Smith, 2008, Algorithms for network interdiction and fortification games Wood, 1993, Deterministic network interdiction, Mathematical and Computer Modelling, 17, 1, 10.1016/0895-7177(93)90236-R I. Akgun, The k-group maximum-flow network-interdiction problem, Master’s Thesis, Naval Postgraduate School, Monterey, CA, March 2000. Di Summa, 2011, Complexity of the critical node problem over trees, Computers and Operations Research, 38, 1766, 10.1016/j.cor.2011.02.016 Kerivin, 2005, Design of survivable networks: a survey, Networks, 46, 1, 10.1002/net.20072 M. Yannakakis, Node-and-edge-deletion NP-complete problems, in: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1978, pp. 253–264. S. Shen, J.C. Smith, Polynomial-time algorithms for disconnecting trees and series–parallel graphs under component connectivity metrics, Networks (2011), in press (http://dx.doi.org/10.1002/net.20464). Gross, 2003 Ahuja, 1993 Garey, 1979 Sherali, 1998, Exploiting special structures in constructing a hierarchy of relaxations for 0–1 mixed integer problems, Operations Research, 46, 396, 10.1287/opre.46.3.396 Hartman, 2010, Dynamic-programming-based inequalities for the capacitated lot-sizing problem, IIE Transactions, 42, 915, 10.1080/0740817X.2010.504683 İ. Büyüktahtakin, Mixed integer programming approaches to lot-sizing and asset replacement problems, Ph.D. Thesis, University of Florida, 2010. ILOG, CPLEX 11.0 User’s Manual, ILOG, Armonk, NY, 2008.