Blossom algorithm: Difference between revisions

Revision as of 23:34, 7 March 2014

Revision as of 08:18, 24 April 2014

Line 92:

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 iterationsiteration 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"/>

The construction procedure considers vertices ''v'' and edges ''e'' in ''G'' and incrementally updates ''F'' as appropriate. If ''v'' is in a tree ''T'' of the forest, we let ''root(v)'' denote the root of ''T''. If both ''u'' and ''v'' are in the same tree ''T'' in ''F'', we let ''distance(u,v)'' denote the length of the unique path from ''u'' to ''v'' in ''T''.