summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
raw | bz2 | zip | gz |
help

author | Peter Kovacs <kpeter@inf.elte.hu> |

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.

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 ///