Computer Science – Discrete Mathematics
Scientific paper
2008-04-22
Computer Science
Discrete Mathematics
Scientific paper
In the matching interdiction problem, we are given an undirected graph with weights and interdiction costs on the edges and seek to remove a subset of the edges constrained to some budget, such that the weight of a maximum weight matching in the remaining graph is minimized. In this work we introduce the matching interdiction problem and show that it is strongly NP-complete even when the input is restricted to simple, bipartite graphs with unit edge weights and unit interdiction costs. Furthermore, we present a pseudo-polynomial algorithm for solving the matching interdiction problem on graphs with bounded treewidth. The proposed algorithm extends the approach that is typically used for the creation of efficient algorithms on graphs with bounded treewidth to interdiction problems.
No associations
LandOfFree
Matching Interdiction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Matching Interdiction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matching Interdiction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-675957