This group contains the algorithms for finding minimum cut in graphs.
The minimum cut problem is to find a non-empty and non-complete \(X\) subset of the nodes with minimum overall capacity on outgoing arcs. Formally, there is a \(G=(V,A)\) digraph, a \(cap: A\rightarrow\mathbf{R}^+_0\) capacity function. The minimum cut is the \(X\) solution of the next optimization problem:
\[ \min_{X \subset V, X\not\in \{\emptyset, V\}} \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \]
LEMON contains several algorithms related to minimum cut problems:
If you want to find minimum cut just between two distinict nodes, see the maximum flow problem.
Classes | |
| class | GomoryHu< GR, CAP > |
| Gomory-Hu cut tree algorithm. More... | |
| class | HaoOrlin< GR, CAP, TOL > |
| Hao-Orlin algorithm for finding a minimum cut in a digraph. More... | |
| class | NagamochiIbaraki< GR, CM, TR > |
| Calculates the minimum cut in an undirected graph. More... | |
| class | GomoryHu< GR, CAP >::MinCutEdgeIt |
| Iterate on the edges of a minimum cut. More... | |
| class | GomoryHu< GR, CAP >::MinCutNodeIt |
| Iterate on the nodes of a minimum cut. More... | |
| struct | NagamochiIbaraki< GR, CM, TR >::SetHeap< H, CR > |
| Named parameter for setting heap and cross reference type More... | |
| struct | NagamochiIbaraki< GR, CM, TR >::SetStandardHeap< H, CR > |
| Named parameter for setting heap and cross reference type with automatic allocation More... | |
| struct | NagamochiIbaraki< GR, CM, TR >::SetUnitCapacity |
Files | |
| file | gomory_hu.h |
| Gomory-Hu cut tree in graphs. | |
| file | hao_orlin.h |
| Implementation of the Hao-Orlin algorithm. | |
| file | nagamochi_ibaraki.h |
| Implementation of the Nagamochi-Ibaraki algorithm. | |
1.8.2
