OJ Board

Hi!

I have a problem with this..

To explain:

We have a graph with n (n is even) nodes... each node is connected to each other by an edge with a positive cost.... We have to match all the nodes in such a way that the cost is minimal..

So I know that there is a fast solution for this problem, but I know only the method O(n^n) with is not the best time


Thanks in advance...

Hi there,

I think that algorithm Kuhn-Munkres is really good. Its time complexity is just O(n^3).

You can take a look at this site:
http://www.mc.edu/campus/users/travis/s ... notes.html

Regards

The Kuhn-Munkres algorithm is for bipartite graphs only.
For general graphs try Edmonds primal-dual algorithm.

Hi!

Thanks for help..

arnsfelt: Could you tell me more about this Edmonds algorithm ( or tell me where could I find it )

Thanks a lot