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

Ignore:
Timestamp:
12/04/07 11:55:27 (12 years ago)
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
 r2514 /** @defgroup min_cut Minimum Cut algorithms @ingroup algs \brief This group describes the algorithms for finding minimum cut in graphs. This group describes the algorithms for finding minimum cut in graphs. @defgroup min_cut Minimum Cut algorithms @ingroup algs \brief This group describes the algorithms for finding minimum cut in graphs. This group describes the algorithms for finding minimum cut in graphs. The minimum cut problem is to find a non-empty and non-complete \f$X\f$ subset of the vertices with minimum overall capacity on outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum cut is the solution of the next optimization problem: \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] The lemon contains several algorithms related to minimum cut problems: - \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut in directed graphs - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for calculate minimum cut in undirected graphs - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all pairs minimum cut in undirected graphs If you want to find minimum cut just between two distinict nodes, please see the \ref max_flow "Maximum Flow page". */