This algorithm allows you to find the minimum weight matching of a bipartite graph. The graph can be of arbitrary size and connectedness. The edge weights are captured by a MxN weight matrix where an infinite(Inf) weight designates that that pair of vertices given by that position are not connected.
I a question about the hungarian algorithm. this algorithm is optimal algorithm for the assignment problem, and the time complexity is O(n^3), right?
But , if the input is the multidimensional matrix, it's possible to use the hungarian algorithm? how does it change the algorithm and the time complexity ?
The algorithm works pretty well I think but I need to find maximum weight matching of a bipartite graph not minimum.
So can I use this code to find the maximum weight matching of a bipartite graph just multiplying the performance matrix with negative. Is there anyone to help me or provide information for finding maximum weight matching.
Thanks in advance.
25 Jul 2008
I hear the author is really hot.
25 Jun 2008
I just found the code has a bug when the cost matrix has some inf elements. For example:
This submission even provides a lot more: A brute-force version for reference, suboptimal (but faster) versions and an implementation as a mex-file which is very fast.
20 Oct 2007
19 Oct 2007
02 Aug 2007
Do you know where i can find a matlab code for maximum weight matching in general graphs?
08 Jul 2007
14 Jun 2007
Great job, works pretty fast too.
But aren't there any algorithm for general graphs and not only for bipartite graphs
04 Jun 2007
* easy to use
* plenty of comments
* doesn't require you to convert your graph to have equal numbers of nodes
* Potentially speed, although I imagine a large amount more work has gone into the BNT version
* Help section could use an example, and an H1 line
I was thrilled that this was here - it was exactly what I needed, and I got it working with no effort at all, really.
Thanks for sharing it.
02 Mar 2007
This works pretty well, but I've found that the hungarian.m function part of the Bayes net toolbox (FullBNT) http://www.cs.ubc.ca/~murphyk/Software/BNT/bnt.html
is approximately twice as fast. It took 17 seconds to process a random 400x400 matrix with the BNT code, whereas this code took 31 sec.
04 Feb 2007
Works great !!! 400 X 400 takes about 32 seconds on 1.6 Ghz Pentium M laptop. And it works. I think this is much better than the other ones posted.
27 Dec 2006
Minh Hoai Nguyen
This works pretty well. I don't know if it could be faster; It took 63s for a random 400*400 matrix.
21 Jul 2006
Bug Fix: Now returns a zero cost if the edge weight matrix is fully disconnected, instead of giving an error.