COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r789 r818  
    317317
    318318This group contains the common graph search algorithms, namely
    319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     320\ref clrs01algorithms.
    320321*/
    321322
     
    325326\brief Algorithms for finding shortest paths.
    326327
    327 This group contains the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
    328330
    329331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    347349
    348350This group contains the algorithms for finding minimum cost spanning
    349 trees and arborescences.
     351trees and arborescences \ref clrs01algorithms.
    350352*/
    351353
     
    356358
    357359This group contains the algorithms for finding maximum flows and
    358 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    359361
    360362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    371373
    372374LEMON contains several algorithms for solving maximum flow problems:
    373 - \ref EdmondsKarp Edmonds-Karp algorithm.
    374 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    375 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    376 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    377 
    378 In most cases the \ref Preflow "Preflow" algorithm provides the
     375- \ref EdmondsKarp Edmonds-Karp algorithm
     376  \ref edmondskarp72theoretical.
     377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
     378  \ref goldberg88newapproach.
     379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
     380  \ref dinic70algorithm, \ref sleator83dynamic.
     381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
     382  \ref goldberg88newapproach, \ref sleator83dynamic.
     383
     384In most cases the \ref Preflow algorithm provides the
    379385fastest method for computing a maximum flow. All implementations
    380386also provide functions to query the minimum cut, which is the dual
     
    394400
    395401This group contains the algorithms for finding minimum cost flows and
    396 circulations. For more information about this problem and its dual
    397 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
    398405
    399406LEMON contains several algorithms for this problem.
    400407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    401    pivot strategies.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    402409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    403    cost scaling.
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
    404412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    405    capacity scaling.
    406  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    407  - \ref CycleCanceling Cycle-Canceling algorithms.
     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.
    408418
    409419In general NetworkSimplex is the most efficient implementation,
     
    441451If you want to find minimum cut just between two distinict nodes,
    442452see the \ref max_flow "maximum flow problem".
     453*/
     454
     455/**
     456@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     457@ingroup algs
     458\brief Algorithms for finding minimum mean cycles.
     459
     460This group contains the algorithms for finding minimum mean cycles
     461\ref clrs01algorithms, \ref amo93networkflows.
     462
     463The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     464of minimum mean length (cost) in a digraph.
     465The mean length of a cycle is the average length of its arcs, i.e. the
     466ratio between the total length of the cycle and the number of arcs on it.
     467
     468This problem has an important connection to \e conservative \e length
     469\e functions, too. A length function on the arcs of a digraph is called
     470conservative if and only if there is no directed cycle of negative total
     471length. For an arbitrary length function, the negative of the minimum
     472cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     473arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     474function.
     475
     476LEMON contains three algorithms for solving the minimum mean cycle problem:
     477- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     478  \ref dasdan98minmeancycle.
     479- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     480  version of Karp's algorithm \ref dasdan98minmeancycle.
     481- \ref Howard "Howard"'s policy iteration algorithm
     482  \ref dasdan98minmeancycle.
     483
     484In practice, the Howard algorithm proved to be by far the most efficient
     485one, though the best known theoretical bound on its running time is
     486exponential.
     487Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     488O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     489applied early termination scheme.
    443490*/
    444491
     
    535582
    536583/**
    537 @defgroup lp_group Lp and Mip Solvers
     584@defgroup lp_group LP and MIP Solvers
    538585@ingroup gen_opt_group
    539 \brief Lp and Mip solver interfaces for LEMON.
    540 
    541 This group contains Lp and Mip solver interfaces for LEMON. The
    542 various LP solvers could be used in the same manner with this
    543 interface.
     586\brief LP and MIP solver interfaces for LEMON.
     587
     588This group contains LP and MIP solver interfaces for LEMON.
     589Various LP solvers could be used in the same manner with this
     590high-level interface.
     591
     592The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     593\ref cplex, \ref soplex.
    544594*/
    545595
Note: See TracChangeset for help on using the changeset viewer.