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:

If you want to find minimum cut just between two distinict nodes, see the maximum flow problem.

Classes

Class

Description

GomoryHu

Gomory-Hu cut tree algorithm.

HaoOrlin

Hao-Orlin algorithm for finding a minimum cut in a digraph.

NagamochiIbaraki

Calculates the minimum cut in an undirected graph.

Other classes of its headers

Class

Description

NagamochiIbarakiDefaultTraits

Default traits class for NagamochiIbaraki class.