3
$\begingroup$

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.

  • 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

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.

  • 2
    The 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_algorithm2011-08-01