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

Timestamp:

12/04/07 11:55:27 (16 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:

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

doc/groups.dox

@@ -259 +259 @@
 
 /**
-@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".
+
 */