| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142860 | Operations Research Letters | 2006 | 6 Pages |
Abstract
The A -matching problem generalizes matching problems by stipulating that the degree of each vertex lies in a set AvAv of admissible values. If these sets have no large “gaps”, the decision problem is in P , while the complexity of the optimization version is open. We present a polynomial time solvable 12-integral linear relaxation for this case.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Robert Carr, Ojas Parekh,