Minimum Cut Algorithms
The same group on the Doxygen site.
- group Minimum Cut Algorithms
Algorithms for finding minimum cut in graphs.
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:
Hao-Orlin algorithm for calculating minimum cut in directed graphs.
Nagamochi-Ibaraki algorithm for calculating minimum cut in undirected graphs.
Gomory-Hu tree computation for calculating all-pairs minimum cut in undirected graphs.
If you want to find minimum cut just between two distinict nodes, see the maximum flow problem.
Classes
Class |
Description |
|---|---|
Gomory-Hu cut tree algorithm. |
|
Hao-Orlin algorithm for finding a minimum cut in a digraph. |
|
Calculates the minimum cut in an undirected graph. |
Other classes of its headers
Class |
Description |
|---|---|
Default traits class for NagamochiIbaraki class. |