Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
b-Matchings and T-Joins
verfasst von : Bernhard Korte, Jens Vygen
Erschienen in: Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
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
In this chapter we introduce two more combinatorial optimization problems, the MAXIMUM WEIGHT b-MATCHING PROBLEM in Section 12.1 and the MINIMUM WEIGHT T -JOIN PROBLEM in Section 12.2. Both can be regarded as generalizations of the MINIMUM WEIGHT PERFECT MATCHING PROBLEM and also include other important problems. On the other hand, both problems can be reduced to theMINIMUM WEIGHT PERFECT MATCHING PROBLEM. They have combinatorial polynomial-time algorithms as well as polyhedral descriptions.