Sep 10, 2001

In [2,3], we have reduced the problem of finding an augmenting path in a general graph to a reachability problem in a directed, bipartite graph, and we have shown that a slight modification of depth-first search leads to an algorithm for finding such paths. This new point of view enables us to give a simplified realization of the Hopcroft-Karp approach for the computation of a maximum cardinality matching in general graphs. We show, how to get an O(n+m) implementation of one phase leading to an O(n^1/2m) algorithm for the computation of a maximum cardinality matching in general graphs.