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://engineeringpapers.com/record/osti%3A956539/network-interdiction-with-budget-constraints
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.