Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a polynomial algorithm to find the max weighted perfect matching in a general graph?

I see that Blossom algorithm can be used to solve the unweighted version of this problem, and I know that this problem can also be reduced to an LP problem (but with exponential numbers of constraints). Is there a way to solve it in polynomial time?

like image 320
xuhdev Avatar asked Jun 29 '15 21:06

xuhdev


1 Answers

Yes, the Blossom algorithm for computing maximum unweighted general matchings can be used in a primal-dual algorithm for maximum weighted general matchings (this is a general technique; the Hungarian algorithm is the bipartite equivalent). There's an implementation called Blossom V due to Vladimir Kolmogorov.

like image 164
David Eisenstat Avatar answered Oct 13 '22 12:10

David Eisenstat