Maximum weight matching 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 ?
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.