Matching Algorithms

Detailed Description

This group contains the algorithms for calculating matchings in graphs and bipartite graphs. The general matching problem is finding a subset of the edges for which each node has at most one incident edge.

There are several different algorithms for calculate matchings in graphs. The matching problems in bipartite graphs are generally easier than in general graphs. The goal of the matching optimization can be finding maximum cardinality, maximum weight or minimum cost matching. The search can be constrained to find perfect or maximum cardinality matching.

The matching algorithms implemented in LEMON:

• MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm for calculating maximum cardinality matching in bipartite graphs.
• PrBipartiteMatching Push-relabel algorithm for calculating maximum cardinality matching in bipartite graphs.
• MaxWeightedBipartiteMatching Successive shortest path algorithm for calculating maximum weighted matching and maximum weighted bipartite matching in bipartite graphs.
• MinCostMaxBipartiteMatching Successive shortest path algorithm for calculating minimum cost maximum matching in bipartite graphs.
• MaxMatching Edmond's blossom shrinking algorithm for calculating maximum cardinality matching in general graphs.
• MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating maximum weighted matching in general graphs.
• MaxWeightedPerfectMatching Edmond's blossom shrinking algorithm for calculating maximum weighted perfect matching in general graphs.
• MaxFractionalMatching Push-relabel algorithm for calculating maximum cardinality fractional matching in general graphs.
• MaxWeightedFractionalMatching Augmenting path algorithm for calculating maximum weighted fractional matching in general graphs.
• MaxWeightedPerfectFractionalMatching Augmenting path algorithm for calculating maximum weighted perfect fractional matching in general graphs.

Classes
class	MaxFractionalMatching< GR, TR >
	Max cardinality fractional matching. More...
class	MaxWeightedFractionalMatching< GR, WM >
	Weighted fractional matching in general graphs. More...
class	MaxWeightedPerfectFractionalMatching< GR, WM >
	Weighted fractional perfect matching in general graphs. More...
class	MaxMatching< GR >
	Maximum cardinality matching in general graphs. More...
class	MaxWeightedMatching< GR, WM >
	Weighted matching in general graphs. More...
class	MaxWeightedPerfectMatching< GR, WM >
	Weighted perfect matching in general graphs. More...
struct	MaxFractionalMatching< GR, TR >::SetElevator< T >
	Named parameter for setting Elevator type More...
struct	MaxFractionalMatching< GR, TR >::SetMatchingMap< T >
	Named parameter for setting MatchingMap type More...
struct	MaxFractionalMatching< GR, TR >::SetStandardElevator< T >
	Named parameter for setting Elevator type with automatic allocation More...
class	MaxWeightedMatching< GR, WM >::BlossomIt
	Iterator for obtaining the nodes of a blossom. More...
class	MaxWeightedPerfectMatching< GR, WM >::BlossomIt
	Iterator for obtaining the nodes of a blossom. More...

Files
file	fractional_matching.h
	Fractional matching algorithms in general graphs.
file	matching.h
	Maximum matching algorithms in general graphs.