Degree Constrained Subgraph Problems and Network Flow Optimization

The cardinality matching problem, one of the most important problems in graph theory, is discussed in terms of a network flow model. From this model, an intuitive and comprehensive theory is developed which brings the previous results and notations of many authors in perspective. Using the theory, the known cardinality matching algorithms are analyzed from a general point of view. These algorithms are also extended to a more general class of network flow problems. In particular, the state-of-the-art cardinality matching algorithm is generalized to obtain strongly polynomial time algorithms for the whole class of non-weighted matching problems. Moreover, we present an algorithm converting fractional into integral matchings. This procedure can be combined with several highly efficient augmentation rules to obtain best-available algorithms for the differet matching problems. Al methods are presented by an object-oriented pseudocode formalism.