There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted matching for that graph with negative weights ?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ Never pick any negative weight edge. $\endgroup$– Tyson WilliamsCommented Dec 19, 2012 at 18:48
-
3$\begingroup$ This is not a research-level question; please see the faq. $\endgroup$– JeffECommented Dec 19, 2012 at 19:13
-
$\begingroup$ What if you want to find a maximal matching? $\endgroup$– Yuval FilmusCommented Dec 20, 2012 at 17:26
-
$\begingroup$ @JeffE The faq says "Ask about [...] computer science at any level." $\endgroup$– domotorpCommented Jan 18, 2023 at 9:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I was only familiar with the Hungarian algorithm which only works for bipartite graphs but I've found something that claims to work for general graphs as well. The basic algorithm is the blossom algorithm, but since you need to find the maximum weight matching you will need Kolmogrov's Blossom V which is based on it.
$\begingroup$
$\endgroup$
Min cost flow finds the minimum weight of the maximum flow in the network. Use {0,1} capacities to turn it to matching. It can be modified for maximum weight.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow3
