How to find the maximum-weight matching

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.

-
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

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.

-

The name is the Hungarian algorithm.

-
+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
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