Blossom algorithm: Difference between revisions

Revision as of 05:06, 17 January 2014

Revision as of 23:34, 7 March 2014

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 augmentingaugmented path==

The search for 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).