Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
b-Matchings and T-Joins
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
Minimum 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 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 these generalized 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.