maximum weight matching

{{short description|Graph theory problem: find a matching with max total weight}}

File:Max weight matching.svg, 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.]]

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.

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.

Algorithms

There is a $O(V^{2}E)$ 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{{Cite journal|last1=Duan|first1=Ran|last2=Pettie|first2=Seth|date=2014-01-01|title=Linear-Time Approximation for Maximum Weight Matching|url=https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf|journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989}} (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.

References

Category:Combinatorial optimization

Category:Computational problems in graph theory