doc/groups.dox
changeset 827 8131c2b9f59a
parent 771 8452ca46e29a
child 865 d48d79b11f5b
equal deleted inserted replaced
39:6bd6d279fbc6 40:af2b89170860
   404 "Minimum Cost Flow Problem".
   404 "Minimum Cost Flow Problem".
   405 
   405 
   406 LEMON contains several algorithms for this problem.
   406 LEMON contains several algorithms for this problem.
   407  - \ref NetworkSimplex Primal Network Simplex algorithm with various
   407  - \ref NetworkSimplex Primal Network Simplex algorithm with various
   408    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
   408    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
   409  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
   409  - \ref CostScaling Cost Scaling algorithm based on push/augment and
   410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
   410    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
   411    \ref bunnagel98efficient.
   411    \ref bunnagel98efficient.
   412  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
   412  - \ref CapacityScaling Capacity Scaling algorithm based on the successive
   413    capacity scaling \ref edmondskarp72theoretical.
   413    shortest path method \ref edmondskarp72theoretical.
   414  - \ref CancelAndTighten The Cancel and Tighten algorithm
   414  - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
   415    \ref goldberg89cyclecanceling.
   415    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
   416  - \ref CycleCanceling Cycle-Canceling algorithms
       
   417    \ref klein67primal, \ref goldberg89cyclecanceling.
       
   418 
   416 
   419 In general NetworkSimplex is the most efficient implementation,
   417 In general NetworkSimplex is the most efficient implementation,
   420 but in special cases other algorithms could be faster.
   418 but in special cases other algorithms could be faster.
   421 For example, if the total supply and/or capacities are rather small,
   419 For example, if the total supply and/or capacities are rather small,
   422 CapacityScaling is usually the fastest algorithm (without effective scaling).
   420 CapacityScaling is usually the fastest algorithm (without effective scaling).