Hungarian method

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Hungarian method

Post by Whinii F. » Fri Mar 05, 2004 9:56 am

Anyone could point out some useful reference or papers to the hungarian method? I tried google and citeseer, and acm portal but I could pick out which is the one I need.

And one more: Are there more than one implementations which are called hungarian methods? I found two differing implementation and they both are called as hungarian. I'm really confused.

Thanks in advance!!! :)
JongMan @ Yonsei

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Mon Mar 08, 2004 10:23 pm

hungarian method is generally for finding perfect matchings in bipartite graphs.
Given a semi-matched graph, you find an augmenting path, that is, a path that starts and ends with an unmatched vertice, and all the edges alternate between matched/unmatched.
So you have: unmatched->matched->unmatched->matched->...->unmatched.
Now if you change all the unmatched into matched, and vice versa, you still have a correctly matched graph, only with one more matching.
Repeat, until you can't find such paths.
This is called a method, because you can make different algorithms out of this, with different complexities or for example for weighed graphs. But this is the general idea. ;)

Post Reply

Return to “Algorithms”