All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages

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

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

## Files | |

file | gomory_hu.h |

Gomory-Hu cut tree in graphs. | |

file | hao_orlin.h |

Implementation of the Hao-Orlin algorithm. | |

Generated on Sat Aug 10 2013 13:58:26 by 1.8.2