diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -406,15 +406,13 @@ LEMON contains several algorithms for this problem. - \ref NetworkSimplex Primal Network Simplex algorithm with various pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. - - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on - cost scaling \ref goldberg90approximation, \ref goldberg97efficient, + - \ref CostScaling Cost Scaling algorithm based on push/augment and + relabel operations \ref goldberg90approximation, \ref goldberg97efficient, \ref bunnagel98efficient. - - \ref CapacityScaling Successive Shortest %Path algorithm with optional - capacity scaling \ref edmondskarp72theoretical. - - \ref CancelAndTighten The Cancel and Tighten algorithm - \ref goldberg89cyclecanceling. - - \ref CycleCanceling Cycle-Canceling algorithms - \ref klein67primal, \ref goldberg89cyclecanceling. + - \ref CapacityScaling Capacity Scaling algorithm based on the successive + shortest path method \ref edmondskarp72theoretical. + - \ref CycleCanceling Cycle-Canceling algorithms, two of which are + strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. diff --git a/lemon/capacity_scaling.h b/lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h +++ b/lemon/capacity_scaling.h @@ -66,7 +66,8 @@ /// /// \ref CapacityScaling implements the capacity scaling version /// of the successive shortest path algorithm for finding a - /// \ref min_cost_flow "minimum cost flow". It is an efficient dual + /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, + /// \ref edmondskarp72theoretical. It is an efficient dual /// solution method. /// /// Most of the parameters of the problem (except for the digraph) diff --git a/lemon/cost_scaling.h b/lemon/cost_scaling.h --- a/lemon/cost_scaling.h +++ b/lemon/cost_scaling.h @@ -90,8 +90,10 @@ /// finding a \ref min_cost_flow "minimum cost flow". /// /// \ref CostScaling implements a cost scaling algorithm that performs - /// push/augment and relabel operations for finding a minimum cost - /// flow. It is an efficient primal-dual solution method, which + /// push/augment and relabel operations for finding a \ref min_cost_flow + /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, + /// \ref goldberg97efficient, \ref bunnagel98efficient. + /// It is a highly efficient primal-dual solution method, which /// can be viewed as the generalization of the \ref Preflow /// "preflow push-relabel" algorithm for the maximum flow problem. ///