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
3
$\begingroup$
graph-theory
-
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.
-
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