![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
Algorithms for finding matchings in graphs and bipartite graphs. More...
Files | |
| file | bipartite_matching.h |
| file | fractional_matching.h |
| file | matching.h |
Classes | |
| class | HopcroftKarp< BPGR > |
| Maximum cardinality matching in bipartite graphs. More... | |
| class | MinCostAssignment< BPGR , CM > |
| Minimum cost assignment in bipartite graphs. More... | |
| 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... | |
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: