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



Download 1.17 Mb.
Page19/19
Date02.05.2018
Size1.17 Mb.
#47336
1   ...   11   12   13   14   15   16   17   18   19
(or the corresponding arc in some shrunken graph) must be examined. When the second such arc is examined, both ends must be even, and a blossom or augmenting path will be found. It cannot be a blossom, or the edge would have been contracted out of existence.
If the algorithm restarts at we don’t need to examine edges in both directions, hence we do not need to replace them by two oppositely directed copies.

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 2022
send message

    Main page