Degree Constrained Subgraph Problems and Network Flow Optimization

Beschreibung

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.

Autor*in

Christian Fremuth-Paeger

Themen in »Degree Constrained Subgraph Problems and Network Flow Optimization«

Korrespondenz in Graphen Matching-Probleme kombinatorische Optimierung

Stimmen zu »Degree Constrained Subgraph Problems and Network Flow Optimization«

Details

Link teilen