Changeset 2514:57143c09dc20 in lemon-0.x for doc/groups.dox
- Timestamp:
- 11/17/07 21:58:11 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3379
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r2500 r2514 224 224 feasible circulations. 225 225 226 \image html flow.png 227 \image latex flow.eps "Graph flow" width=\textwidth 226 The maximum flow problem is to find a flow between a single-source and 227 single-target that is maximum. Formally, there is \f$G=(V,A)\f$ 228 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity 229 function and given \f$s, t \in V\f$ source and target node. The 230 maximum flow is the solution of the next optimization problem: 231 232 \f[ 0 \le f_a \le c_a \f] 233 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f] 234 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] 235 236 The lemon contains several algorithms for solve maximum flow problems: 237 - \ref lemon::EdmondsKarp "Edmonds-Karp" 238 - \ref lemon::Preflow "Goldberg's Preflow algorithm" 239 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree" 240 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" 241 242 In most cases the \ref lemon::Preflow "preflow" algorithm provides the 243 fastest method to compute the maximum flow. All impelementations 244 provides functions for query the minimum cut, which is the dual linear 245 programming probelm of the maximum flow. 246 228 247 */ 229 248
Note: See TracChangeset
for help on using the changeset viewer.