Anzeige
Erschienen in:
2004 | OriginalPaper | Buchkapitel
A TDI Description of Restricted 2-Matching Polytopes
verfasst von : Gyula Pap
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We give a TDI description for a class of polytopes, which corresponds to a restricted 2-matching problem. The perfect matching polytope, triangle-free perfect 2-matching polytope and relaxations of the travelling salesman polytope are members of this class. The paper shows that 2-matching problems for which the unweighted problem was known to be tractable, the weighted is also tractable.