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:

- Hao-Orlin algorithm for calculating minimum cut in directed 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... | |

## Files | |

file | gomory_hu.h |

Gomory-Hu cut tree in graphs. | |

file | hao_orlin.h |

Implementation of the Hao-Orlin algorithm. |

Generated on Wed Nov 9 2011 11:44:10 by 1.7.3