abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Minimum Cut Algorithms

Algorithms for finding minimum cut in graphs. More...

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.

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...

Detailed Description

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.