| Article ID: | iaor19961285 |
| Country: | Netherlands |
| Volume: | 65 |
| Issue: | 2 |
| Start Page Number: | 139 |
| End Page Number: | 150 |
| Publication Date: | Jun 1994 |
| Journal: | Mathematical Programming (Series A) |
| Authors: | Cunningham William H., Green-Krtki Jan |
| Keywords: | programming: integer |
A matchable set of a graph is a set of vertices joined in pairs by disjoint edges. Balas and Pulleyblank gave a linear-inequality description of the convex hull of matchable sets. The authors give a polynomial-time combinatorial algorithm for the separation problem for this polytope, and a min-max theorem characterizing the maximum violation by a given point of an inequality of the system.