diff -r 26983135fd6d -r 57143c09dc20 doc/groups.dox --- a/doc/groups.dox Wed Nov 14 17:53:08 2007 +0000 +++ b/doc/groups.dox Sat Nov 17 20:58:11 2007 +0000 @@ -223,8 +223,27 @@ This group describes the algorithms for finding maximum flows and feasible circulations. -\image html flow.png -\image latex flow.eps "Graph flow" width=\textwidth +The maximum flow problem is to find a flow between a single-source and +single-target that is maximum. Formally, there is \f$G=(V,A)\f$ +directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity +function and given \f$s, t \in V\f$ source and target node. The +maximum flow is the solution of the next optimization problem: + +\f[ 0 \le f_a \le c_a \f] +\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f] +\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] + +The lemon contains several algorithms for solve maximum flow problems: +- \ref lemon::EdmondsKarp "Edmonds-Karp" +- \ref lemon::Preflow "Goldberg's Preflow algorithm" +- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree" +- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" + +In most cases the \ref lemon::Preflow "preflow" algorithm provides the +fastest method to compute the maximum flow. All impelementations +provides functions for query the minimum cut, which is the dual linear +programming probelm of the maximum flow. + */ /**