89 /// \brief Implementation of the Cost Scaling algorithm for |
89 /// \brief Implementation of the Cost Scaling algorithm for |
90 /// finding a \ref min_cost_flow "minimum cost flow". |
90 /// finding a \ref min_cost_flow "minimum cost flow". |
91 /// |
91 /// |
92 /// \ref CostScaling implements a cost scaling algorithm that performs |
92 /// \ref CostScaling implements a cost scaling algorithm that performs |
93 /// push/augment and relabel operations for finding a \ref min_cost_flow |
93 /// push/augment and relabel operations for finding a \ref min_cost_flow |
94 /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, |
94 /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation, |
95 /// \ref goldberg97efficient, \ref bunnagel98efficient. |
95 /// \cite goldberg97efficient, \cite bunnagel98efficient. |
96 /// It is a highly efficient primal-dual solution method, which |
96 /// It is a highly efficient primal-dual solution method, which |
97 /// can be viewed as the generalization of the \ref Preflow |
97 /// can be viewed as the generalization of the \ref Preflow |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
98 /// "preflow push-relabel" algorithm for the maximum flow problem. |
99 /// It is a polynomial algorithm, its running time complexity is |
99 /// It is a polynomial algorithm, its running time complexity is |
100 /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost. |
100 /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost. |