All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Files
Matching Algorithms
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:

matching.png

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.