Minimal Perfect Matching in Full Graphs...

cyfra · Post by **cyfra** » Fri Jan 03, 2003 10:50 am

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...

babe · Post by **babe** » Fri Jan 03, 2003 4:00 pm

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

arnsfelt · Post by **arnsfelt** » Fri Jan 03, 2003 4:17 pm

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

cyfra · Post by **cyfra** » Sat Jan 04, 2003 11:57 am

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