Sep 10, 2001

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.