Content deleted Content added
Line 89:
Thus blossoms can be contracted and search performed in the contracted graphs. This reduction is at the heart of Edmonds's algorithm.
==Finding an
The search for an augmenting path uses an auxiliary data structure consisting of a [[forest (graph theory)|forest]] ''F'' whose individual trees correspond to specific portions of the graph ''G''. In fact, the forest ''F'' is the same that would be used to find maximum matchings in [[bipartite graph]]s (without need for shrinking blossoms).
In each iterations the algorithm either (1) finds an augmenting path, (2) finds a blossom and recurses onto the corresponding contracted graph, or (3) concludes there are no augmenting paths. The auxiliary structure is built by an incremental procedure discussed next.<ref name = "tarjan notes"/>
| |||