A SEPARATION ALGORITHM FOR THE MATCHABLE SET POLYTOPE

Authors
CUNNINGHAM WH GREENKROTKI J
Citation
Wh. Cunningham et J. Greenkrotki, A SEPARATION ALGORITHM FOR THE MATCHABLE SET POLYTOPE, Mathematical programming, 65(2), 1994, pp. 139-150
Citations number
9
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
65
Issue
2
Year of publication
1994
Pages
139 - 150
Database
ISI
SICI code
0025-5610(1994)65:2<139:ASAFTM>2.0.ZU;2-K
Abstract
A matchable set of a graph is a set of vertices joined in pairs by dis joint edges. Balas and Pulleyblank gave a linear-inequality descriptio n of the convex hull of matchable sets. We give a polynomial-time conb inatorial algorithm for the separation problem for this polytope, and a min-max theorem characterizing the maximum violation by a given poin t of an inequality of the system.