Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just iteratively finding a augmenting path and complementing it. I am talking about edmond blossom algorithm.

Edit: http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching/

this is what I was looking for in the first step we have only 13 edges and we can not find any augmenting path.

now due to bloosom contrast we have increased matching by 1 edge.

  • 1
    $\begingroup$ Apparently the difficulty is finding augmenting paths in non-bipartite graphs. Do you have any algorithm in mind? $\endgroup$ – Yuval Filmus Apr 5 '19 at 20:33
  • 2
    $\begingroup$ This might run into problems if there are odd cycles. See for example Section 3 here: cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. $\endgroup$ – Yuval Filmus Apr 5 '19 at 20:37
  • 1
    $\begingroup$ The algorithm in Section 3 is only guaranteed to find an augmenting path in bipartite graphs. Perhaps you have a different algorithm in mind. $\endgroup$ – Yuval Filmus Apr 5 '19 at 21:11
  • 1
    $\begingroup$ It’s all in Section 3. Read it carefully. $\endgroup$ – Yuval Filmus Apr 5 '19 at 21:21
  • 2
    $\begingroup$ Edmonds’ algorithm finds a maximum matching in any graph. $\endgroup$ – Yuval Filmus Apr 6 '19 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.