author Peter Kovacs Thu, 12 Nov 2009 23:52:51 +0100 changeset 879 25804ef35064 parent 878 4b1b378823dc child 880 0643a9c2c3ae
Add citations to the scaling MCF algorithms (#180, #184)
and improve the doc of their group.
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/capacity_scaling.h file | annotate | diff | comparison | revisions lemon/cost_scaling.h file | annotate | diff | comparison | revisions
     1.1 --- a/doc/groups.dox	Thu Nov 12 23:49:05 2009 +0100
1.2 +++ b/doc/groups.dox	Thu Nov 12 23:52:51 2009 +0100
1.3 @@ -406,15 +406,13 @@
1.4  LEMON contains several algorithms for this problem.
1.5   - \ref NetworkSimplex Primal Network Simplex algorithm with various
1.6     pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
1.7 - - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
1.8 -   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
1.9 + - \ref CostScaling Cost Scaling algorithm based on push/augment and
1.10 +   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
1.11     \ref bunnagel98efficient.
1.12 - - \ref CapacityScaling Successive Shortest %Path algorithm with optional
1.13 -   capacity scaling \ref edmondskarp72theoretical.
1.14 - - \ref CancelAndTighten The Cancel and Tighten algorithm
1.15 -   \ref goldberg89cyclecanceling.
1.16 - - \ref CycleCanceling Cycle-Canceling algorithms
1.17 -   \ref klein67primal, \ref goldberg89cyclecanceling.
1.18 + - \ref CapacityScaling Capacity Scaling algorithm based on the successive
1.19 +   shortest path method \ref edmondskarp72theoretical.
1.20 + - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
1.21 +   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
1.22
1.23  In general NetworkSimplex is the most efficient implementation,
1.24  but in special cases other algorithms could be faster.

     2.1 --- a/lemon/capacity_scaling.h	Thu Nov 12 23:49:05 2009 +0100
2.2 +++ b/lemon/capacity_scaling.h	Thu Nov 12 23:52:51 2009 +0100
2.3 @@ -66,7 +66,8 @@
2.4    ///
2.5    /// \ref CapacityScaling implements the capacity scaling version
2.6    /// of the successive shortest path algorithm for finding a
2.7 -  /// \ref min_cost_flow "minimum cost flow". It is an efficient dual
2.8 +  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
2.9 +  /// \ref edmondskarp72theoretical. It is an efficient dual
2.10    /// solution method.
2.11    ///
2.12    /// Most of the parameters of the problem (except for the digraph)

     3.1 --- a/lemon/cost_scaling.h	Thu Nov 12 23:49:05 2009 +0100
3.2 +++ b/lemon/cost_scaling.h	Thu Nov 12 23:52:51 2009 +0100
3.3 @@ -90,8 +90,10 @@
3.4    /// finding a \ref min_cost_flow "minimum cost flow".
3.5    ///
3.6    /// \ref CostScaling implements a cost scaling algorithm that performs
3.7 -  /// push/augment and relabel operations for finding a minimum cost
3.8 -  /// flow. It is an efficient primal-dual solution method, which
3.9 +  /// push/augment and relabel operations for finding a \ref min_cost_flow
3.10 +  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
3.11 +  /// \ref goldberg97efficient, \ref bunnagel98efficient.
3.12 +  /// It is a highly efficient primal-dual solution method, which
3.13    /// can be viewed as the generalization of the \ref Preflow
3.14    /// "preflow push-relabel" algorithm for the maximum flow problem.
3.15    ///