Blossom algorithm: Difference between revisions

Revision as of 21:44, 18 November 2013

Revision as of 15:49, 3 January 2014

Line 141:

[[File:forest expansion.png|400px|alt=Forest expansion on line B10]]

Next, it detects a blossom and contracts the graph (lines B20 – B22B21).

[[File:blossom contraction.png|400px|alt=Blossom contraction on line B21]]

Finally, it locates an augmenting path P′ in the contracted graph (line B23B22) and lifts it to the original graph (line B24B23). Note that the ability of the algorithm to contract blossoms is crucial here; the algorithm can not find ''P'' in the original graph directly because only out-of-forest edges between vertices at even distances from the roots are considered on line B17 of the algorithm.

[[File:path detection.png|400px|alt=Detection of augmenting path P′ in G′ on line B17]]