COIN-OR::LEMON - Graph Library

Changeset 879:25804ef35064 in lemon


Ignore:
Timestamp:
11/12/09 23:52:51 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Rebase:
65336539373836373466333030303164666633626635373132396336363436646237366435313232
Message:

Add citations to the scaling MCF algorithms (#180, #184)
and improve the doc of their group.

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r818 r879  
    407407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    408408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    409  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    410    cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     410   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    411411   \ref bunnagel98efficient.
    412  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    413    capacity scaling \ref edmondskarp72theoretical.
    414  - \ref CancelAndTighten The Cancel and Tighten algorithm
    415    \ref goldberg89cyclecanceling.
    416  - \ref CycleCanceling Cycle-Canceling algorithms
    417    \ref klein67primal, \ref goldberg89cyclecanceling.
     412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     413   shortest path method \ref edmondskarp72theoretical.
     414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     415   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    418416
    419417In general NetworkSimplex is the most efficient implementation,
  • lemon/capacity_scaling.h

    r878 r879  
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow". It is an efficient dual
     69  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
     70  /// \ref edmondskarp72theoretical. It is an efficient dual
    7071  /// solution method.
    7172  ///
  • lemon/cost_scaling.h

    r878 r879  
    9191  ///
    9292  /// \ref CostScaling implements a cost scaling algorithm that performs
    93   /// push/augment and relabel operations for finding a minimum cost
    94   /// flow. It is an efficient primal-dual solution method, which
     93  /// push/augment and relabel operations for finding a \ref min_cost_flow
     94  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
     95  /// \ref goldberg97efficient, \ref bunnagel98efficient.
     96  /// It is a highly efficient primal-dual solution method, which
    9597  /// can be viewed as the generalization of the \ref Preflow
    9698  /// "preflow push-relabel" algorithm for the maximum flow problem.
Note: See TracChangeset for help on using the changeset viewer.