| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142194 | Operations Research Letters | 2014 | 5 Pages |
Abstract
We consider the problem of maximally decreasing the edge-connectivity of an edge-weighted graph by removing a limited set of edges. This problem, which we term connectivity interdiction, falls into a large family of so-called interdiction problems, which have been considered in a variety of contexts. Whereas little is known about the approximability of most interdiction problems, we show that connectivity interdiction admits a PTAS, and a natural special case of it can even be solved efficiently.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rico Zenklusen,