Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2001 Copyright 2001 Universität Bonn, Institut für Informatik, Abt. V

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
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope