Maximum weight matching

A special case of it is the assignment problem, in which the input is restricted to be a bipartite graph, and the matching constrained to be have cardinality that of the smaller of the two partitions.

time algorithm to find a maximum matching or a maximum weight matching in a graph that is not bipartite; it is due to Jack Edmonds, is called the paths, trees, and flowers method or simply Edmonds' algorithm, and uses bidirected edges.

A generalization of the same technique can also be used to find maximum independent sets in claw-free graphs.

More elaborate algorithms exist and are reviewed by Duan and Pettie[1] (see Table III).

Their work proposes an approximation algorithm for the maximum weight matching problem, which runs in linear time for any fixed error bound.

Maximum weight matching of 2 graphs. The first is also a perfect matching , while the second is far from it with 4 vertices unaccounted for, but has high value weights compared to the other edges in the graph.