COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
12/28/07 12:00:51 (13 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:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r2530 r2548  
    319319for find matchings in graphs and bipartite graphs.
    320320
    321 This group provides some algorithm objects and function
    322 to calculate matchings in graphs and bipartite graphs.
     321This group provides some algorithm objects and function to calculate
     322matchings in graphs and bipartite graphs. The general matching problem is
     323finding a subset of the edges which does not shares common endpoints.
     324 
     325There are several different algorithms for calculate matchings in
     326graphs.  The matching problems in bipartite graphs are generally
     327easier than in general graphs. The goal of the matching optimization
     328can be the finding maximum cardinality, maximum weight or minimum cost
     329matching. The search can be constrained to find perfect or
     330maximum cardinality matching.
     331
     332Lemon contains the next algorithms:
     333- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     334  augmenting path algorithm for calculate maximum cardinality matching in
     335  bipartite graphs
     336- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     337  algorithm for calculate maximum cardinality matching in bipartite graphs
     338- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     339  Successive shortest path algorithm for calculate maximum weighted matching
     340  and maximum weighted bipartite matching in bipartite graph
     341- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     342  Successive shortest path algorithm for calculate minimum cost maximum
     343  matching in bipartite graph
     344- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     345  for calculate maximum cardinality matching in general graph
     346- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     347  shrinking algorithm for calculate maximum weighted matching in general
     348  graph
     349- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     350  Edmond's blossom shrinking algorithm for calculate maximum weighted
     351  perfect matching in general graph
    323352
    324353\image html bipartite_matching.png
Note: See TracChangeset for help on using the changeset viewer.