Balanced network flows. VIII. A revised theory of phase-ordered algorithms and the O(√(n)mlog(n2/m)/log n) bound for the nonbipartite cardinality matching problem

Balanced network flows. VIII. A revised theory of phase-ordered algorithms and the O(√(n)mlog(n2/m)/log n) bound for the nonbipartite cardinality matching problem

0.00 Avg rating0 Votes
Article ID: iaor20033294
Country: United States
Volume: 41
Issue: 3
Start Page Number: 137
End Page Number: 142
Publication Date: Mar 2003
Journal: Networks
Authors: ,
Keywords: matching
Abstract:

This paper closes some gaps in the discussion of nonweighted balanced network flow problems. These gaps all concern the phase-ordered augmentation algorithm, which can be viewed as the matching counterpart of the Dinic max-flow algorithm. We show that this algorithm runs in O(n2m) time compared to the bound of O(nm2) derived in Part III of this series and that the bipartiteness requirement can be omitted. The result which deserves attention is the complexity bound for the cardinality matching problem which was shown for the bipartite case by Feder and Motwani. This bound was previously claimed for the general case in a preprint of Goldberg and Karzanov but omitted in later versions of this paper.

Reviews

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