COIN-OR::LEMON - Graph Library

Changeset 869:636dadefe1e6 in lemon-1.2


Ignore:
Timestamp:
09/25/09 21:51:36 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Add fractional matching algorithms (#314)

Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r710 r869  
    350350problem of maximum flow.
    351351
    352 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     352\ref Circulation is a preflow push-relabel algorithm implemented directly
    353353for finding feasible circulations, which is a somewhat different problem,
    354354but it is strongly related to maximum flow.
     
    471471  Edmond's blossom shrinking algorithm for calculating maximum weighted
    472472  perfect matching in general graphs.
     473- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     474  maximum cardinality fractional matching in general graphs.
     475- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     476  maximum weighted fractional matching in general graphs.
     477- \ref MaxWeightedPerfectFractionalMatching
     478  Augmenting path algorithm for calculating maximum weighted
     479  perfect fractional matching in general graphs.
    473480
    474481\image html bipartite_matching.png
  • lemon/Makefile.am

    r708 r869  
    8282        lemon/fib_heap.h \
    8383        lemon/fourary_heap.h \
     84        lemon/fractional_matching.h \
    8485        lemon/full_graph.h \
    8586        lemon/glpk.h \
  • test/CMakeLists.txt

    r698 r869  
    2222  error_test
    2323  euler_test
     24  fractional_matching_test
    2425  gomory_hu_test
    2526  graph_copy_test
  • test/Makefile.am

    r698 r869  
    2020        test/error_test \
    2121        test/euler_test \
     22        test/fractional_matching_test \
    2223        test/gomory_hu_test \
    2324        test/graph_copy_test \
     
    6667test_error_test_SOURCES = test/error_test.cc
    6768test_euler_test_SOURCES = test/euler_test.cc
     69test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
    6870test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
    6971test_graph_copy_test_SOURCES = test/graph_copy_test.cc
Note: See TracChangeset for help on using the changeset viewer.