Sketchy Notes on Edmonds’ Incredible Shrinking Blossom Algorithm for General Matching



Download 1.17 Mb.
Page15/19
Date02.05.2018
Size1.17 Mb.
#47336
1   ...   11   12   13   14   15   16   17   18   19
and
If is labeled even] with stop: augmenting path found.
If is labeled stop: blossom found.
(If is labeled do nothing.)
(*)On finding a blossom, shrink it into an even vertex and continue (or restart on the shrunken graph).
On finding an augmenting path, expand all blossoms in reverse order of shrinking, adding edges to the augmenting path to keep it an augmenting path after each blossom expansion. Having found an augmenting path in the original graph, switch matched and unmatched edges along it to increase the size of the matching by one. Restart.


Download 1.17 Mb.

Share with your friends:
1   ...   11   12   13   14   15   16   17   18   19




The database is protected by copyright ©ininet.org 2024
send message

    Main page