Top Qs
Timeline
Chat
Perspective

Maximum weight matching

Graph theory problem: find a matching with max total weight From Wikipedia, the free encyclopedia

Maximum weight matching
Remove ads
Remove ads

In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized.

Thumb
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.

A special case of the maximum weight matching problem is the assignment problem, in which the graph is a bipartite graph and the matching must have cardinality equal to that of the smaller of the two partitions. Another special case is the problem of finding a maximum cardinality matching on an unweighted graph: this corresponds to the case where all edge weights are the same.

Remove ads

Algorithms

There is a 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.

Remove ads

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads