Blossom algorithm: Difference between revisions

Revision as of 19:22, 9 June 2018

Revision as of 06:07, 7 July 2018

Line 82:

[[File:Edmonds blossom.svg|500px|alt=Example of a blossom]]

''G’'' has an ''M’''-augmenting path [[if and only if|if and only if]] ''G'' has an ''M''-augmenting path, and that any ''M’''-augmenting path ''P’'' in ''G’'' can be '''lifted''' to an ''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''.<ref name = "tarjan notes">{{citation

| author = Tarjan, Robert

| contribution = Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching

Line 165:

| author1 = Kenyon, Claire

| author2 = Lovász, László

| authorlink2 = László Lovász

| contribution = Algorithmic Discrete Mathematics

| title = Technical Report CS-TR-251-90, Department of Computer Science, Princeton University