Minimum Cut Algorithms

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:

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

Detailed Description

Classes

Files