455 /** |
455 /** |
456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms |
456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms |
457 @ingroup algs |
457 @ingroup algs |
458 \brief Algorithms for finding minimum mean cycles. |
458 \brief Algorithms for finding minimum mean cycles. |
459 |
459 |
460 This group contains the algorithms for finding minimum mean cycles. |
460 This group contains the algorithms for finding minimum mean cycles |
|
461 \ref clrs01algorithms, \ref amo93networkflows. |
461 |
462 |
462 The \e minimum \e mean \e cycle \e problem is to find a directed cycle |
463 The \e minimum \e mean \e cycle \e problem is to find a directed cycle |
463 of minimum mean length (cost) in a digraph. |
464 of minimum mean length (cost) in a digraph. |
464 The mean length of a cycle is the average length of its arcs, i.e. the |
465 The mean length of a cycle is the average length of its arcs, i.e. the |
465 ratio between the total length of the cycle and the number of arcs on it. |
466 ratio between the total length of the cycle and the number of arcs on it. |
471 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
472 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
472 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
473 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
473 function. |
474 function. |
474 |
475 |
475 LEMON contains three algorithms for solving the minimum mean cycle problem: |
476 LEMON contains three algorithms for solving the minimum mean cycle problem: |
476 - \ref Karp "Karp"'s original algorithm. |
477 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, |
|
478 \ref dasdan98minmeancycle. |
477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved |
479 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved |
478 version of Karp's algorithm. |
480 version of Karp's algorithm \ref dasdan98minmeancycle. |
479 - \ref Howard "Howard"'s policy iteration algorithm. |
481 - \ref Howard "Howard"'s policy iteration algorithm |
|
482 \ref dasdan98minmeancycle. |
480 |
483 |
481 In practice, the Howard algorithm proved to be by far the most efficient |
484 In practice, the Howard algorithm proved to be by far the most efficient |
482 one, though the best known theoretical bound on its running time is |
485 one, though the best known theoretical bound on its running time is |
483 exponential. |
486 exponential. |
484 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
487 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |