ISSN:
1436-4646
Keywords:
Combinatorial optimization
;
Polyhedra
;
Matching
;
Matchable set
;
Separation algorithm
;
Augmenting path
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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. We 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581694
Permalink