405 shortest path method \ref edmondskarp72theoretical. |
405 shortest path method \ref edmondskarp72theoretical. |
406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
406 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
407 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
408 |
408 |
409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient |
409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient |
410 implementations, but the other two algorithms could be faster in special cases. |
410 implementations, but the other algorithms could be faster in special cases. |
411 For example, if the total supply and/or capacities are rather small, |
411 For example, if the total supply and/or capacities are rather small, |
412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). |
412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling). |
|
413 |
|
414 These classes are intended to be used with integer-valued input data |
|
415 (capacities, supply values, and costs), except for \ref CapacityScaling, |
|
416 which is capable of handling real-valued arc costs (other numerical |
|
417 data are required to be integer). |
413 */ |
418 */ |
414 |
419 |
415 /** |
420 /** |
416 @defgroup min_cut Minimum Cut Algorithms |
421 @defgroup min_cut Minimum Cut Algorithms |
417 @ingroup algs |
422 @ingroup algs |
446 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms |
451 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms |
447 @ingroup algs |
452 @ingroup algs |
448 \brief Algorithms for finding minimum mean cycles. |
453 \brief Algorithms for finding minimum mean cycles. |
449 |
454 |
450 This group contains the algorithms for finding minimum mean cycles |
455 This group contains the algorithms for finding minimum mean cycles |
451 \ref clrs01algorithms, \ref amo93networkflows. |
456 \ref amo93networkflows, \ref karp78characterization. |
452 |
457 |
453 The \e minimum \e mean \e cycle \e problem is to find a directed cycle |
458 The \e minimum \e mean \e cycle \e problem is to find a directed cycle |
454 of minimum mean length (cost) in a digraph. |
459 of minimum mean length (cost) in a digraph. |
455 The mean length of a cycle is the average length of its arcs, i.e. the |
460 The mean length of a cycle is the average length of its arcs, i.e. the |
456 ratio between the total length of the cycle and the number of arcs on it. |
461 ratio between the total length of the cycle and the number of arcs on it. |
462 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
467 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
463 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
468 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
464 function. |
469 function. |
465 |
470 |
466 LEMON contains three algorithms for solving the minimum mean cycle problem: |
471 LEMON contains three algorithms for solving the minimum mean cycle problem: |
467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, |
472 - \ref KarpMmc Karp's original algorithm \ref karp78characterization. |
468 \ref dasdan98minmeancycle. |
|
469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved |
473 - \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. |
471 - \ref HowardMmc Howard's policy iteration algorithm |
475 - \ref HowardMmc Howard's policy iteration algorithm |
472 \ref dasdan98minmeancycle. |
476 \ref dasdan98minmeancycle, \ref dasdan04experimental. |
473 |
477 |
474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the |
478 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the |
475 most efficient one, though the best known theoretical bound on its running |
479 most efficient one, though the best known theoretical bound on its running |
476 time is exponential. |
480 time is exponential. |
477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |
481 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |