Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have a graph with a set of edge, and a weight assigned to each edge. How can I find a maximum-weight matching of the edges? I think this is a classic CO problem but I don't know the name of the algorithm. I need this algorithm to solve an online programming puzzle.

share|improve this question
    
Do you mean for graphs in general, or only for bipartite graphs? –  Mike Spivey Aug 1 '11 at 11:25
    
@Mike Spivey: I am dealing with complete graphs. where every vertex could be adjacent to every other vertex. –  Mark Aug 1 '11 at 17:29

2 Answers 2

up vote 2 down vote accepted

Many books on operations research have material about matchings and weighted matchings, often only for the bipartite graph case. However, a book that treats both the general and bipartite case is Dieter Jungnickel, Graphs, Networks and Algorithms, Springer, 1999, Chapters 12 and 13.

share|improve this answer

The name is the Hungarian algorithm.

share|improve this answer
    
+1 it looks like the algorithm is suppose to find the minimum weight. I suppose if I just reverse the algorithm then I will find the maximum weight... –  Mark Aug 1 '11 at 7:25
    
Negate the values, yes. –  Peter Taylor Aug 1 '11 at 7:41
2  
The Hungarian algorithm is for bipartite graphs. This is not a bipartite graph. You need Edmonds's algorithm: en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm –  Robert Israel Aug 1 '11 at 18:50

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.