Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
85231

Sep 10, 2001

Maximum Matching in General Graphs Without Explicit Consideration of Blossoms
Norbert Blum
[Download PostScript] [Download PDF]

We reduce the problem of finding an augmenting path in a general graph to a reachability problem in a directed, bipartite graph. Furthermore, we show that a slight modification of depth-first search leads to an algorithm for finding such paths. This new point of view enables us to develop algorithms for the solution of matching problems without explicit analysis of blossoms, nested blossoms, a.s.o. A variant of Edmonds' primal-dual method for the weighted matching problem which uses the modified depth-first search instead of Edmonds' maximum matching algorithm as a subroutine is described. Furthermore, a straightforward O(nm log n)-implementation of this algorithm is given.

Last Change: 08/16/04 at 12:31:52
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V