Premium
Reductions to 1–matching polyhedra
Author(s) -
Aráoz Julian,
Cunningham William H.,
Edmonds Jack,
GreenKrótki Jan
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130403
Subject(s) - polyhedron , mathematics , matching (statistics) , disjoint sets , combinatorics , regular polygon , discrete mathematics , dual (grammatical number) , graph , convex hull , art , statistics , geometry , literature
The matching polyhedron theorem of Edmonds and Johnson, which gives the convex hull of capacitated perfect b ‐matchings of a bidirected graph, is proved by reducing this matching problem to the ordinary perfect 1–matching problem, for which there exists a short inductive proof of the corresponding polyhedral theorem. The proof method makes it possible to deduce nestedness and discreteness properties of optimal dual solutions to the general matching problem from analogous properties of optimal dual solutions to the perfect 1–matching problem. In particular, the total dual half‐integrality of the inequality system for general matching is shown to follow from that for 1–matching. Applications considered include determining the convex hull of unions of disjoint circuits of a graph.