LEDA Guide: Maximum Weighted Matching in General Graphs

> LEDA Guide > Graph Algorithms > Matching Algorithms > Maximum Weighted Matching in General Graphs

Maximum Weighted Matching in General Graphs

What is a Maximum Weighted Matching in a General Graph?

A matching in a graph G=(V,E) is a subset M of the edges E such that no two edges in M share a common end node. If the edges of the graph have an associated weight, then a maximum weighted matching is a matching such that the sum of the weights of the edges in the matching is maximum.

We use the term general graph to indicate that the graph is not bipartite. Matchings in bipartite graphs can be computed more efficiently than matchings in general (=non-bipartite) graphs.

Intuition Maximum Weighted Matching in General Graphs: Suppose we have a set of workers. These are the nodes in our graph. We want to build pairs of workers that work together. For each pair of workers we know the profit we get if the two work together. This defines the weights of the edges of the graph. In the maximum weighted matching problem we want to find pairs of workers such that the total profit is maximum.

Edge Weight Restrictions

The algorithm for maximum weighted matching in general graphs uses divisions. So, in order to avoid rounding errors for the number type int, please make sure that all edge weights are multiplicatives of four. Note that the algorithm will automatically multiply all edge weights by four if this condition is not met. Moreover, all edge weights must be non-negative. Remark: Multiplying all edge weights by a constant factor f does not change the maximum weighted matchings of a graph. Only the weight of each matching is f times bigger.

LEDA Functions for Maximum Weighted Matching

MAX_WEIGHT_MATCHING() computes a maximum weighted matching in a general graph with non-negative edge weights. By default the result of the computation is checked internally. This check can be disabled. There is also an explicit check function available. However, using this explicit check functions is quite complicated.

Example of MAX_WEIGHT_MATCHING()

Running times

For a graph G=(V,E), the running times of computing maximum weighted matching is O(|V|*|E|log|V|)). The checking functions are linear in the size of the graph.

Tips