Maximum Matching in General Graphs Without Explicit Consideration of Blossoms Revisited

Norbert Blum

We reduce the problem of finding an augmenting path in a general graph to a reachability problem in a directed bipartite graph. A slight modification of depth-first search leads to…