This group contains the algorithms for finding minimum cut in graphs.
The minimum cut problem is to find a non-empty and non-complete subset of the nodes with minimum overall capacity on outgoing arcs. Formally, there is a
digraph, a
capacity function. The minimum cut is the
solution of the next optimization problem:
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... | |
Files | |
file | gomory_hu.h |
Gomory-Hu cut tree in graphs. | |
file | hao_orlin.h |
Implementation of the Hao-Orlin algorithm. |