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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.