Balanced network flows. I. A unifying framework for design and analysis of matching algorithms

Balanced network flows. I. A unifying framework for design and analysis of matching algorithms

0.00 Avg rating0 Votes
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: ,
Keywords: graphs
Abstract:

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 c-capacitated b-matching algorithm can be derived that behaves like the Dinic algorithm for the maximum flow problem. It will turn out that techniques for the maximum flow problem can be applied to matching problems much more explicitly than done before. A comprehensive duality theory depending on the network flow model used here will follow. Explicit algorithms for nonweighted problems will be presented in subsequent papers.

Reviews

Required fields are marked *. Your email address will not be published.