Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 ?

share|improve this question
4  
Never pick any negative weight edge. –  Tyson Williams Dec 19 '12 at 18:48
3  
This is not a research-level question; please see the faq. –  JeffE Dec 19 '12 at 19:13
    
What if you want to find a maximal matching? –  Yuval Filmus Dec 20 '12 at 17:26
add comment

migrated from cstheory.stackexchange.com Dec 20 '12 at 14:37

This question came from our site for theoretical computer scientists and researchers in related fields.

2 Answers

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.