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.
How to find the maximum-weight matching
2
$\begingroup$
graph-theory
-
0Do you mean for graphs in general, or only for bipartite graphs? – 2011-08-01
-
0@Mike Spivey: I am dealing with complete graphs. where every vertex could be adjacent to every other vertex. – 2011-08-01
2 Answers
2
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.
-
0"It would make little sense to describe an algorithm for the weighted matching problem in general graphs without using more of the theory of linear programming; for this reason, no such algorithm is presented in this book." – 2017-05-14
2
The name is the Hungarian algorithm.
-
0+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... – 2011-08-01
-
0Negate the values, yes. – 2011-08-01
-
2The Hungarian algorithm is for bipartite graphs. This is not a bipartite graph. You need Edmonds's algorithm: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm – 2011-08-01