DOE OSTI · 956539
Network interdiction with budget constraints
Abstract
Several scenarios exist in the modern interconnected world which call for efficient network interdiction algorithms. Applications are varied, including computer network security, prevention of spreading of Internet worms, policing international smuggling networks, controlling spread of diseases and optimizing the operation of large public energy grids. In this paper we consider some natural network optimization questions related to the budget constrained interdiction problem over general graphs. Many of these questions turn out to be computationally hard to tackle. We present a particularly interesting practical form of the interdiction question which we show to be computationally tractable. A polynomial time algorithm is then presented for this problem.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Santhi, Nankakishore, Pan, Feng. 2009-01-01. Network interdiction with budget constraints. https://www.osti.gov/biblio/956539
Cite the original work for its findings. Save a collection to share your selection of sources.