Blossom algorithm: Difference between revisions

Revision as of 09:05, 19 February 2015

Revision as of 13:41, 19 February 2015

Line 144:

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

Finally, it locates an augmenting path P′ in the contracted graph (line B22) and lifts it to the original graph (line B23). Note that the ability of the algorithm to contract blossoms is crucial here; the algorithm can notcannot 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]]