COIN-OR::LEMON - Graph Library

Changeset 2530:f86f7e4eb2ba in lemon-0.x for doc/groups.dox


Ignore:
Timestamp:
12/04/07 11:55:27 (12 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3407
Message:

Reimplementation of Hao-Orlin algorithm
Little modifictaion in NagamochiIbaraki?
More docs for minimum cut algorithms

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r2514 r2530  
    259259
    260260/**
    261 @defgroup min_cut Minimum Cut algorithms
    262 @ingroup algs
    263 \brief This group describes the algorithms
    264 for finding minimum cut in graphs.
    265 
    266 This group describes the algorithms
    267 for finding minimum cut in graphs.
     261@defgroup min_cut Minimum Cut algorithms
     262@ingroup algs
     263
     264\brief This group describes the algorithms for finding minimum cut in
     265graphs.
     266
     267This group describes the algorithms for finding minimum cut in graphs.
     268
     269The minimum cut problem is to find a non-empty and non-complete
     270\f$X\f$ subset of the vertices with minimum overall capacity on
     271outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     272\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     273cut is the solution of the next optimization problem:
     274
     275\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     276
     277The lemon contains several algorithms related to minimum cut problems:
     278
     279- \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut
     280  in directed graphs 
     281- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     282  calculate minimum cut in undirected graphs
     283- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all
     284  pairs minimum cut in undirected graphs
     285
     286If you want to find minimum cut just between two distinict nodes,
     287please see the \ref max_flow "Maximum Flow page".
     288
    268289*/
    269290
Note: See TracChangeset for help on using the changeset viewer.