Weighted Perfect Matching in General GraphsWhat is a Weighted Perfect Matching?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. A perfect matchingM
in G is a matching such that each node of G is
incident to an edge in M . If the edges of the graph have an
associated weight, then a maximum (minimum) weighted perfect matching
is a perfect matching such that the sum of the weights of the edges in the
matching is maximum (minimum).
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 Perfect Matching: 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 perfect matching problem we want to find pairs of workers such that all workers have a mate and the total profit is maximum. Edge Weight RestrictionsThe algorithms for weighted perfect matching in general graphs use divisions.
So, in order to avoid rounding errors for the number type LEDA Functions for Weighted Perfect Matching
Example
of Running timesFor a graphG=(V,E) , the running times of computing weighted
perfect matchings is O(|V|*|E|log|V|)). The checking functions are linear
in the size of the graph.
TipsComputing weighted perfect matchings in a graph is very complicated. Checking the result is much easier. Moreover, checking is only linear in the size of the graph. So, the overhead is quite small. We recommend to use the internal checking functions to ensure the correctness of the result. |
See also:Maximum Cardinality Matching in General Graphs Maximum Weighted Matching in General Graphs Bipartite Maximum Weighted Matching Bipartite Maximum Weighted Maximum Cardinality Matching Maximum Cardinality Matching in Bipartite Graphs Manual Entries: Manual Page General Weighted Matching |