Integer and Fractional Matchings.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
We examine the connections between maximum cardinality edge matchings in a graph and optimal solutions to the associated linear program, which we call maximum f-matchings fractional matchings. We say that a maximum matching M separates an odd cycle with vertex set S, if M has no edge with exactly one end in S. An odd cycle is separable if it is separated by at least one maximum matching. We show that a graph G has a maximum f-matching that is integer, if and only if it has no separable odd cycles the minimum number q of vertex-disjoint odd cycles for which a maximum f-matching has fractional components, equals the maximum number s of vertex-disjoint odd cycles, separated by a maximum matching the difference between the cardinality of a maximum f-matching and that of a maximum matching in G is one half times s any maximum f-matching with fractional components for a minimum number s of vertex-disjoint odd cycles defines a maximum matching obtainable from it in s steps and if a maximum f-matching has fractional components for a set Q of odd cycles that is not minimum, there exists another maximum f-matching with fractional components for a minimum-cardinality set S of odd cycles, such that S is a subset of Q, absival QS is even, and the cycles in QS are pairwise connected by alternating paths. Author
- Numerical Mathematics