0
$\begingroup$

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf

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.

Improve this question
$\endgroup$
12
  • 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, 2019 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, 2019 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, 2019 at 21:11
  • 1
    $\begingroup$ It’s all in Section 3. Read it carefully. $\endgroup$
    – Yuval Filmus
    Apr 5, 2019 at 21:21
  • 2
    $\begingroup$ Edmonds’ algorithm finds a maximum matching in any graph. $\endgroup$
    – Yuval Filmus
    Apr 6, 2019 at 7:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.