JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Nice one. | Reply
Nice article. Currently, I am doing my final year project about a bipartite graph matching and this can be a good reference. :)
Re: Nice one. (response to post by jan_holmes) | Reply
Very nice tutorial :)

Some weeks ago i tried to implement the hungarian algorithm but failed, this tutorial comes in the right time :)

Just one question, are there better algorithms to find the maximum/minimum weight perfect matching in bipartite grahps? [like O(N^2 log N ) ..]
Re: Nice one. (response to post by mogers) | Reply
You can use fast matrix multiplication to get a better runtime but it won't be faster in practice, I guess ;)
Re: Nice one. (response to post by gawry) | Reply
Would you mind to give me an example of that method ?
Re: Nice one. (response to post by jan_holmes) | Reply
I don't know how it works. You might try reading this paper.
Re: Nice one. (response to post by gawry) | Reply
Hey, I am noob here and so am learning from the maters...!

How would the algorithm change if we had to find the max i.e. match such that you get the max sum of the cost?

Thanks.
Re: Nice one. (response to post by ravihasija) | Reply
Invert the sign of all weights. Then just run the matching as described here.
Re: Nice one. (response to post by jan_holmes) | Reply
It is very nice article, but at step 3 of O(n3) algorithm it should J(Gl)/T not T/J(Gl). I know it is minor mistake and in coding part it is implemented according J(Gl)/T but can lead confusion in readers mind who does not have time to check coding part out.
RSS