Maximum weight matching

In computer science, 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 it is the assignment problem, in which the input is restricted to be a bipartite graph. 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 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.

gollark: I like milk, but cereal with milk is hereßy.
gollark: Praise the __flying__ spaghetti **monster**.
gollark: I dislike how browsers made CSRF a thing, it is total bees.
gollark: One of these days I really ought to add login and CSRF prevention.
gollark: ```javascriptimport m = require("mithril")import * as RPCTypes from "../common/rpc"export const sendMessage = (msg: RPCTypes.Message): Promise<RPCTypes.MessageResponse> => { return m.request( { method: "POST", url: "./rpc/", body: msg, }).then(res => { const [ type, p1, p2 ] = res if (type === "error") { throw new RPCTypes.RPCError(p2, p1) } else if (type === "ok") { return p1 } else { throw new Error("Invalid RPC response") } })}const handler = { get: (target, prop) => (...args) => sendMessage([prop, ...args])}export const serverProxy = new Proxy({}, handler)```

References
  1. Duan, Ran; Pettie, Seth (2014-01-01). "Linear-Time Approximation for Maximum Weight Matching" (PDF). Journal of the ACM. doi:10.1145/2529989.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.