Matching Interdiction

Details Matching Interdiction Matching Interdiction

2008-04-22

arxiv.org/abs/0804.3583v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-675957