2002 | OriginalPaper | Buchkapitel
b-Matchings and T-Joins
verfasst von : Bernhard Korte, Jens Vygen
Erschienen in: 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
In this chapter we introduce two more combinatorial optimization problems, the Minimum Weightb-Matching Problem in Section 12.1 and the Minimum WeightT-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 the Minimum Weight Perfect Matching Problem. They have combinatorial polynomial-time algorithms as well as polyhedral descriptions. Since in both cases the Separation Problem turns out to be solvable in polynomial time, we obtain another polynomial-time algorithm for the general matching problems (using the Ellipsoid Method; see Section 4.6). In fact, the Separation Problem can be reduced to finding a minimum capacity T-cut in both cases; see Sections 12.3 and 12.4. This problem, finding a minimum capacity cut δ(X) such that |X ∩ T| is odd for a specified vertex set T, can be solved with network flow techniques.