Changes in lemon/cycle_canceling.h [1013:f6f6896a4724:1053:1c978b5bcc65] in lemon-main
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r1013 r1053 48 48 /// \ref CycleCanceling implements three different cycle-canceling 49 49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" 50 /// \ ref amo93networkflows, \refklein67primal,51 /// \ refgoldberg89cyclecanceling.50 /// \cite amo93networkflows, \cite klein67primal, 51 /// \cite goldberg89cyclecanceling. 52 52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 53 53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. 54 /// It runs in strongly polynomial time , but in practice, it is typically55 /// orders of magnitude slower than the scaling algorithms and56 /// \ref NetworkSimplex.54 /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)), 55 /// but in practice, it is typically orders of magnitude slower than 56 /// the scaling algorithms and \ref NetworkSimplex. 57 57 /// (For more information, see \ref min_cost_flow_algs "the module page".) 58 58 /// … … 132 132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a 133 133 /// well-known strongly polynomial method 134 /// \ refgoldberg89cyclecanceling. It improves along a134 /// \cite goldberg89cyclecanceling. It improves along a 135 135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 136 136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). … … 138 138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an 139 139 /// improved version of the previous method 140 /// \ refgoldberg89cyclecanceling.140 /// \cite goldberg89cyclecanceling. 141 141 /// It is faster both in theory and in practice, its running time 142 142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
Note: See TracChangeset
for help on using the changeset viewer.