Article ID: | iaor20022481 |
Country: | United States |
Volume: | 33 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 28 |
Publication Date: | Jan 1999 |
Journal: | Networks |
Authors: | Jungnickel Dieter, Fremuth-Paeger Christian |
Keywords: | graphs |
We discuss a wide range of matching problems in terms of a network flow model. More than this, we start up a matching theory which is very intuitive and independent from the original graph context. This first paper contains a standardized theory for the performance analysis of augmentation algorithms in a wide area of matching problems. Several optimality criteria are given which do not use cuts or barriers. As an application of our theory, the known cardinality matching algorithms of Edmonds, Kameda and Munro, and Micali and Vazirani, and the algorithm of Kocay and Stone for capacitated matching problems can be studied in their effects. From our theory a