COIN-OR::LEMON - Graph Library

Changeset 1002:f63ba40a60f4 in lemon-main


Ignore:
Timestamp:
01/30/12 23:24:14 (12 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve module docs and references (#437)

Files:
6 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r919 r1002  
    408408
    409409In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
    410 implementations, but the other two algorithms could be faster in special cases.
     410implementations, but the other algorithms could be faster in special cases.
    411411For example, if the total supply and/or capacities are rather small,
    412412\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     413
     414These classes are intended to be used with integer-valued input data
     415(capacities, supply values, and costs), except for \ref CapacityScaling,
     416which is capable of handling real-valued arc costs (other numerical
     417data are required to be integer).
    413418*/
    414419
     
    449454
    450455This group contains the algorithms for finding minimum mean cycles
    451 \ref clrs01algorithms, \ref amo93networkflows.
     456\ref amo93networkflows, \ref karp78characterization.
    452457
    453458The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    465470
    466471LEMON contains three algorithms for solving the minimum mean cycle problem:
    467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
    468   \ref dasdan98minmeancycle.
     472- \ref KarpMmc Karp's original algorithm \ref karp78characterization.
    469473- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    470   version of Karp's algorithm \ref dasdan98minmeancycle.
     474  version of Karp's algorithm \ref hartmann93finding.
    471475- \ref HowardMmc Howard's policy iteration algorithm
    472   \ref dasdan98minmeancycle.
     476  \ref dasdan98minmeancycle, \ref dasdan04experimental.
    473477
    474478In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
  • doc/min_cost_flow.dox

    r877 r1002  
    102102\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    103103
    104 However if the sum of the supply values is zero, then these two problems
     104However, if the sum of the supply values is zero, then these two problems
    105105are equivalent.
    106106The \ref min_cost_flow_algs "algorithms" in LEMON support the general
  • doc/references.bib

    r904 r1002  
    55  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and
    66                  {O}ptimization in {N}etworks},
    7   howpublished = {\url{http://lemon.cs.elte.hu/}},
    8   year =         2009
     7  howpublished = {\url{http://lemon.cs.elte.hu/}}
    98}
    109
     
    212211  volume =       23,
    213212  pages =        {309-311}
     213}
     214
     215@article{hartmann93finding,
     216  author =       {Mark Hartmann and James B. Orlin},
     217  title =        {Finding minimum cost to time ratio cycles with small
     218                  integral transit times},
     219  journal =      {Networks},
     220  year =         1993,
     221  volume =       23,
     222  pages =        {567-574}
    214223}
    215224
     
    226235}
    227236
     237@article{dasdan04experimental,
     238  author =       {Ali Dasdan},
     239  title =        {Experimental analysis of the fastest optimum cycle
     240                  ratio and mean algorithms},
     241  journal =      {ACM Trans. Des. Autom. Electron. Syst.},
     242  year =         2004,
     243  volume =       9,
     244  issue =        4,
     245  pages =        {385-418}
     246}
     247
    228248
    229249%%%%% Minimum cost flow algorithms %%%%%
  • lemon/hartmann_orlin_mmc.h

    r879 r1002  
    9999  /// This class implements the Hartmann-Orlin algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
     101  /// \ref hartmann93finding, \ref dasdan98minmeancycle.
    102102  /// It is an improved version of \ref KarpMmc "Karp"'s original algorithm,
    103103  /// it applies an efficient early termination scheme.
  • lemon/howard_mmc.h

    r877 r1002  
    9999  /// This class implements Howard's policy iteration algorithm for finding
    100100  /// a directed cycle of minimum mean cost in a digraph
    101   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
     101  /// \ref dasdan98minmeancycle, \ref dasdan04experimental.
    102102  /// This class provides the most efficient algorithm for the
    103103  /// minimum mean cycle problem, though the best known theoretical
  • lemon/karp_mmc.h

    r877 r1002  
    9999  /// This class implements Karp's algorithm for finding a directed
    100100  /// cycle of minimum mean cost in a digraph
    101   /// \ref amo93networkflows, \ref dasdan98minmeancycle.
     101  /// \ref karp78characterization, \ref dasdan98minmeancycle.
    102102  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    103103  ///
Note: See TracChangeset for help on using the changeset viewer.