<p>Two years ago, when researching the (unweighted) blossom algorithm, I found two great sets of notes, one by Tarjan and one by Zwick. They made the unweighted case seem quite straightforward and I was able to implement it in Mathematica using recursion. It works quite well. </p>

<p>The notes that I found useful are</p>

<p><a href="http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf">http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf</a>
and
<a href="http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf">http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf</a></p>

<p>They distill it all down to very simple terms that allow one to think recursively and then, as noted, program recursively. </p>

<p>I think it should all work in the weighted case, which I trying to get implemented now. </p>

CC BY-SA 3.0
2011-12-24T01:55:58.443Z
And I have demos that can be watched by anyone with the free software: The first one shows blossom nicely....                 <http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching>                              <http://demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm>                                                                                                                                  <http://demonstrations.wolfram.com/PlacingDominoesOnACheckerboard>
Stan Wagon
CC BY-SA 3.0
2011-12-29T16:27:13.490Z
And I have just programmed unweighted blossom as given in Korte/Vygen. I see a couple of speedups are possible to his code (eg, start with a maximal matching, as opposed to nothing), but the nice thing is that his procedural code is given in a form that one can easily translate to working code. Next: weighted blossom, which is much harder.
Stan Wagon
CC BY-SA 3.0
2011-12-20T04:24:36.693Z
2011-12-20T04:24:36.693Z
Stan Wagon
<p>Edmonds's matching algorithm (also called Blossom Algorithm) solves the maximum matching on general graphs. Actually it is a generalization of alternating paths method. (I am not sure of the name of the method but it shoud be König-Hall method.) It basically finds augmenting paths (see wikipedia page: <a href="http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm">http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm</a>) to extend the current matching and stops if there is no more augmenting paths. In general graphs, the only problem occurs in odd cycles. In the Edmonds's matching algorithm odd cycles are contracted (blossoms) and expended back to have a solution.</p>

<p>There is also a correspondence between Blossom Algorithm and Primal Dual method.
Odd cycles cause fractional extreme points. Therefore we add so called blossom inequalities for each odd cycle.</p>

<p>Minimum weighted perfect matching and maximum weight matching problems could also be handled with this approach.</p>

<p>For details of the algorithm, see
<a href="http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm">http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm</a>
http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf</p>

<p>For mathematical formulation and the corresponding primal-dual method, see
<a href="http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf">http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf</a></p>

CC BY-SA 2.5
2010-12-25T08:12:08.297Z
2010-12-25T08:12:08.297Z
Arman
<p>The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight <strong>bipartite</strong> matching problem in polynomial time and anticipated the later development of the important <em>primal-dual method</em>. The algorithm was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian algorithm" because the algorithm was based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. Munkres reviewed the algorithm in 1957 and observed that it is indeed polytime. Since then the algorithm is also known as Kuhn-Munkres algorithm.</p>

<p>Although the Hungarian contains the basic idea of the primal-dual method, it solves the maximum weight bipartite matching problem directly without using any linear programming (LP) machinery. 
Thus, in answer of the following <a href="https://cstheory.stackexchange.com/questions/2707/justification-for-the-hungarian-method-kuhn-munkres">question</a>, Jukka Suomela commented </p>

<blockquote>
  <p>Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance. [...] You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.</p>
</blockquote>

<p>In other words, you don't have to worry about how to round a rational/floating point solution from the LP solver to get back a maximum weight perfect matching of a given bipartite graph.</p>

<p>My question is the following:</p>

<blockquote>
  <p>Is there a generalization of the Hungarian algorithm that works for general <strong>undirected graph</strong> without the use of LP machinery similarly to the spirit of the original Hungarian algorithm?</p>
</blockquote>

<p>I would prefer modern and easy-to-read exposition instead of some original complicated paper. But any pointer will be very appreciated!</p>

<p>Many thanks in advance and Merry Christmas!!!</p>

<hr>

<p><strong>Update:</strong> The question is nicely answered by Arman below. I just want to point out that another nice source to study the Edmonds's Blossom Algorithm (for the  weighted case) is Chapter 11 of  <a href="http://rads.stackoverflow.com/amzn/click/3540718435" rel="nofollow noreferrer"><em>Combinatorial Optimization</em> by Korte and Vygen</a>. Google book actually  shows nearly all the parts I need to understand the algorithm.</p>

CC BY-SA 2.5
2010-12-24T16:16:51.830Z
How about Edmonds's matching algorithm?
http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
Arman
CC BY-SA 2.5
2010-12-24T17:03:32.913Z
@Arman - That's what I was thinking, too.  Thanks for the link, Wikipedia has a surprisingly detailed exposition of Edmond's blossom algorithm.
Abraham Flaxman
CC BY-SA 2.5
2010-12-24T17:13:09.997Z
By the way, Edmonds's matching algorithm is also based on Primal-Dual method.
Arman
CC BY-SA 2.5
2010-12-24T17:13:59.327Z
Thanks Arman. The wikipedia link also points to the book "Lovász, László; Plummer, Michael (1986). Matching Theory" for the weighted version of Edmonds's algorithm. I should really check that book out. Thank you very much for your comments! Maybe if any of you can explain in high level of how the algorithm generalizes the Hungarian algorithm, you can definitely make it an answer.
Dai Le
CC BY-SA 2.5
2010-12-25T05:09:26.327Z
I think it's a pretty good answer as is :). Arman, you should add it as such
Suresh Venkat
<graph-theory><reference-request><graph-algorithms><linear-programming><primal-dual>
Generalization of the Hungarian algorithm to general undirected graphs?
Dai Le
# Generalization of the Hungarian algorithm to general undirected graphs?

(Asked by: username_0 on 2010-12-24)

The Hungarian algorithm is a combinatorial optimization algorithm which solves the maximum weight **bipartite** matching problem in polynomial time and anticipated the later development of the important *primal-dual method*. The algorithm was developed and published by Harold Kuhn in 1955, who gave the name "Hungarian algorithm" because the algorithm was based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. Munkres reviewed the algorithm in 1957 and observed that it is indeed polytime. Since then the algorithm is also known as Kuhn-Munkres algorithm.

Although the Hungarian contains the basic idea of the primal-dual method, it solves the maximum weight bipartite matching problem directly without using any linear programming (LP) machinery.
Thus, in answer of the following [question](https://cstheory.stackexchange.com/questions/2707/justification-for-the-hungarian-method-kuhn-munkres), Jukka Suomela commented

> Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance. [...] You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.

In other words, you don't have to worry about how to round a rational/floating point solution from the LP solver to get back a maximum weight perfect matching of a given bipartite graph.

My question is the following:

> Is there a generalization of the Hungarian algorithm that works for general **undirected graph** without the use of LP machinery similarly to the spirit of the original Hungarian algorithm?

I would prefer modern and easy-to-read exposition instead of some original complicated paper. But any pointer will be very appreciated!

Many thanks in advance and Merry Christmas!!!

---

**Update:** The question is nicely answered by Arman below. I just want to point out that another nice source to study the Edmonds's Blossom Algorithm (for the weighted case) is Chapter 11 of [*Combinatorial Optimization* by Korte and Vygen](http://rads.stackoverflow.com/amzn/click/3540718435). Google book actually shows nearly all the parts I need to understand the algorithm.

**Tags:** graph-theory, reference-request, graph-algorithms, linear-programming, primal-dual
> **Comments:**
> **username_1**: How about Edmonds's matching algorithm? http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm  
> **username_2**: @Arman - That's what I was thinking, too.  Thanks for the link, Wikipedia has a surprisingly detailed exposition of Edmond's blossom algorithm.  
> **username_1**: By the way, Edmonds's matching algorithm is also based on Primal-Dual method.  
> **username_0**: Thanks Arman. The wikipedia link also points to the book "Lovász, László; Plummer, Michael (1986). Matching Theory" for the weighted version of Edmonds's algorithm. I should really check that book out. Thank you very much for your comments! Maybe if any of you can explain in high level of how the algorithm generalizes the Hungarian algorithm, you can definitely make it an answer.  
> **username_3**: I think it's a pretty good answer as is :). Arman, you should add it as such  

---

## 2 answers

### Answer by username_1 on 2010-12-25. Score: 16 | Accepted answer

Edmonds's matching algorithm (also called Blossom Algorithm) solves the maximum matching on general graphs. Actually it is a generalization of alternating paths method. (I am not sure of the name of the method but it shoud be König-Hall method.) It basically finds augmenting paths (see wikipedia page: <http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm>) to extend the current matching and stops if there is no more augmenting paths. In general graphs, the only problem occurs in odd cycles. In the Edmonds's matching algorithm odd cycles are contracted (blossoms) and expended back to have a solution.

There is also a correspondence between Blossom Algorithm and Primal Dual method.
Odd cycles cause fractional extreme points. Therefore we add so called blossom inequalities for each odd cycle.

Minimum weighted perfect matching and maximum weight matching problems could also be handled with this approach.

For details of the algorithm, see
<http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm>
http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

For mathematical formulation and the corresponding primal-dual method, see
<http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf>


---

### Answer by username_4 on 2011-12-20. Score: 9

Two years ago, when researching the (unweighted) blossom algorithm, I found two great sets of notes, one by Tarjan and one by Zwick. They made the unweighted case seem quite straightforward and I was able to implement it in Mathematica using recursion. It works quite well.

The notes that I found useful are

<http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf>
and
<http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf>

They distill it all down to very simple terms that allow one to think recursively and then, as noted, program recursively.

I think it should all work in the weighted case, which I trying to get implemented now.

> **Comments:**
> **username_4**: And I have demos that can be watched by anyone with the free software: The first one shows blossom nicely....                 <http://demonstrations.wolfram.com/TheBlossomAlgorithmForMaximumMatching>                              <http://demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm>                                                                                                                                  <http://demonstrations.wolfram.com/PlacingDominoesOnACheckerboard>  
> **username_4**: And I have just programmed unweighted blossom as given in Korte/Vygen. I see a couple of speedups are possible to his code (eg, start with a maximal matching, as opposed to nothing), but the nice thing is that his procedural code is given in a form that one can easily translate to working code. Next: weighted blossom, which is much harder.  

---

