DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA067067
Title:
Integer and Fractional Matchings.
Corporate Author:
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Report Date:
1979-02-01
Abstract:
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
Descriptive Note:
Management sciences research rept.,
Pages:
0023
Contract Number:
N00014-75-C-0621
Contract Number 2:
NSF-MPS73-08534
File Size:
8.41MB
