Blossom algorithm: Difference between revisions

Revision as of 18:24, 30 December 2014

Revision as of 09:05, 19 February 2015

Line 77:

| title = Course Notes, Department of Computer Science, Princeton University

| url = http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf

}}</ref> that ''G’'' has an ''M’''-augmenting path [[if and only if|iff]] ''G'' has an ''M''-augmenting path, and that any ''M’''-augmenting path ''P’'' in ''G’'' can be '''lifted''' to aan ''M''-augmenting path in ''G'' by undoing the contraction by ''B'' so that the segment of ''P’'' (if any) traversing through ''v_B'' is replaced by an appropriate segment traversing through ''B''. In more detail:

* if ''P’'' traverses through a segment ''u → v_B → w'' in ''G’'', then this segment is replaced with the segment ''u → ( u’ → ... → w’ ) → w'' in ''G'', where blossom vertices ''u’'' and ''w’'' and the side of ''B'', ''( u’ → ... → w’ )'', going from ''u’'' to ''w’'' are chosen to ensure that the new path is still alternating (''u’'' is exposed with respect to <math>M \cap B</math>, <math>\{ w', w \} \in E \setminus M</math>).