Changeset 2548:a3ba22ebccc6 in lemon-0.x for doc

Timestamp:

12/28/07 12:00:51 (16 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3425

Message:

Edmond's Blossom shrinking algroithm:
MaxWeightedMatching?
MaxWeightedPerfectMatching?

File:

• doc/groups.dox (modified) (1 diff)

doc/groups.dox

@@ -319 +319 @@
 for find matchings in graphs and bipartite graphs.
 
-This group provides some algorithm objects and function
-to calculate matchings in graphs and bipartite graphs.
+This group provides some algorithm objects and function to calculate
+matchings in graphs and bipartite graphs. The general matching problem is
+finding a subset of the edges which does not shares common endpoints.
+ 
+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 the finding maximum cardinality, maximum weight or minimum cost
+matching. The search can be constrained to find perfect or
+maximum cardinality matching.
+
+Lemon contains the next algorithms:
+- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
+  augmenting path algorithm for calculate maximum cardinality matching in 
+  bipartite graphs
+- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
+  algorithm for calculate maximum cardinality matching in bipartite graphs 
+- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
+  Successive shortest path algorithm for calculate maximum weighted matching 
+  and maximum weighted bipartite matching in bipartite graph
+- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
+  Successive shortest path algorithm for calculate minimum cost maximum 
+  matching in bipartite graph
+- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
+  for calculate maximum cardinality matching in general graph
+- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
+  shrinking algorithm for calculate maximum weighted matching in general
+  graph
+- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
+  Edmond's blossom shrinking algorithm for calculate maximum weighted
+  perfect matching in general graph
 
 \image html bipartite_matching.png