Abstract
Assessing the vulnerability of network infrastructure to disruptive events is recognized as an important component of network planning and analysis. Motivations for this type of research range from searching for the most effective/ efficient means of disrupting a network (e.g., preventing drug trafficking — see Wood 1993) to assessing possible threats to critical network infrastructures so that adequate protective measures can be devised to limit potential disruption (see Wu 1992). In such analysis, the disruptive activity being examined, whether due to natural disaster, accident, or sabotage, can be generically referred to as network interdiction.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Naval Research Logistics
- Operation Research Letter
- Stochastic Integer Program
- Network Vulnerability
- Network Risk
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abilene. 2005. http://abilene.internet2.edu.
Balcioglu, A. and R.K. Wood. 2003. Enumerating near-min s-t cuts. In Network Interdiction and Stochastic Integer Programming. Edited by D.L. Woodruff. Boston: Kluwer Academic Publishers, 51–69.
Ball, M.O., B.L. Golden, and R.V. Vohra. 1989. Finding the most vital arcs in a network. Operations Research Letters. 8(2), 73–76.
Burch, C., R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg. 2003. A decomposition-based approximation for network inhibition. In Network Interdiction and Stochastic Integer Programming. Edited by D.L. Woodruff. Boston: Kluwer Academic Publishers, 51–69.
Boyle, M.R. 1998. Partial-Enumeration for Planar Network Interdiction Problems. M.S. Thesis: Naval Postgraduate School.
C|net News.com. 2006. Sprint Nextel suffers service outage. http://www.news.com. Monday, Jan. 9.
Church, R.L., M.P. Scaparra, and R.S. Middleton. 2004. Identifying critical infrastructure: the median and covering facility interdiction problems. Annals of the Association of American Geographers. 94(3), 491–502.
Colbourn, C.J. 1987. The Combinatorics of Network Reliability. New York: Oxford.
Corley, H.W. and H. Chang. 1974. Finding the n most vital nodes in a flow network. Management Science. 21, 362–364.
Corley, H.W. and D.Y. Sha. 1982. Most vital links and nodes in weighted networks. Operations Research Letters. 1(4), 157–160.
CNN.com. 2006. Cut cable quiets Sprint service in West. http://www.cnn.com. Jan. 9.
Cunningham, W.H. 1985. Optimal attack and reinforcement of a network. Journal of the Association for Computing Machinery. 32(3), 549–561.
Doyle, J.C., D.L. Alderson, L. Li, S. Low, M. Roughan, S. Shalunov, R. Tanaka, and W. Willinger. 2005. The “Robust Yet Fragile” Nature of the Internet. Proceedings of the National Academy of Sciences of the United States of America. 102(4), 14497–14502.
Evans, J. and E. Minieka. 1992. Optimization Algorithms for Networks and Graphs. 2nd Edition. New York: Marcel Dekker, Inc.
Ford, L.R. and D.R. Fulkerson. 1962. Flows in Networks. Princeton Press.
Ghare, P.M., D.C. Montgomery, and W.C. Turner. 1971. Optimal interdiction policy for a flow network. Naval Research Logistics Quarterly. 18, 37–45.
Grubesic, T.H., M.E. O’Kelly, and A.T. Murray. 2003. A geographic perspective on commercial internet survivability. Telematics and Informatics. 20, 51–69.
Grubesic, T.H., T.C. Matisziw, and A.T. Murray. 2006. Targeted attacks and survivability in critical network infrastructure. Submitted for publication.
Holme, P., B.J. Kim, C.N. Yoon, and S.K. Han. 2002. Attack vulnerability of complex networks. Physical Review E. 65, 056109.
Malik, K., A.K. Mittal, and S.K. Gupta. 1989. The most vital arcs in the shortest path problem. Operations Research Letters. 8, 223–227.
Matisziw, T.C., A.T. Murray, and T.H. Grubesic. 2006. Exploring the vulnerability of network infrastructure to interdiction. Submitted for review.
McMasters, A.W. and T.M. Mustin. 1970. Optimal interdiction of a supply network. Naval Research Logistics Quarterly. 17, 261–268.
Murray, A.T., T.C. Matisziw, and T.H. Grubesic. 2007. Critical network infrastructure analysis: interdiction and system flow. Journal of Geographical Systems, 39.
Murray-Tuite, P.M. and H.S. Mahmassani. 2004. Methodology for determining vulnerable links in a transportation network. Transportation Research Record. 1882, 88–96.
Myung, Y-S. and H. Kim. 2004. A cutting plane algorithm for computing k-edge survivability of a network. European Journal of Operational Research. 156, 579–589.
Phillips, C.A. 1993. The network inhibition problem. Proceedings of the Annual Association for Computing Machinery STOC. California, May.
Ratliff, H.D., G.T. Sicilia, and S.H. Lubore. 1975. Finding the n most vital links in flow networks. Management Science. 21(5), 531–539.
Wollmer, R. 1964. Removing arcs from a network. Operations Research. 12, 934–40.
Wood, R. K. 1993. Deterministic network interdiction. Mathematical Computer Modelling. 17(2), 1–18.
Wu, T-H. 1992. Fiber Network Service Survivability. Boston: Artech House.
Wu, T-H., D.J. Kolar, and R.H. Cardwell. 1988. Survivable network architectures for broad-band fiber optic networks: model and performance comparison. Journal of Lightwave Technology. 6(11), 1698–1709.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Matisziw, T.C., Murray, A.T., Grubesic, T.H. (2007). Bounding Network Interdiction Vulnerability Through Cutset Identification. In: Murray, A.T., Grubesic, T.H. (eds) Critical Infrastructure. Advances in Spatial Science. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68056-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-68056-7_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68055-0
Online ISBN: 978-3-540-68056-7
eBook Packages: Business and EconomicsEconomics and Finance (R0)