| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141894 | Discrete Optimization | 2007 | 8 Pages |
Abstract
Given an edge-weighted graph, the induced matching problem is an edge packing problem, which asks to find a maximum weight edge set such that every edge in the graph is adjacent to at most one edge in the set. In this paper, we generalize this problem by introducing edge capacities and propose an approximation algorithm to the problem. The analysis of this algorithm is based on a relationship between two polytopes for an LP relaxation of the above problem and the capacitated bb-matching problem.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Takuro Fukunaga, Hiroshi Nagamochi,