261 |
261 |
262 \sa \ref concepts::Heap "Heap concept" |
262 \sa \ref concepts::Heap "Heap concept" |
263 */ |
263 */ |
264 |
264 |
265 /** |
265 /** |
266 @defgroup matrices Matrices |
|
267 @ingroup datas |
|
268 \brief Two dimensional data storages implemented in LEMON. |
|
269 |
|
270 This group contains two dimensional data storages implemented in LEMON. |
|
271 */ |
|
272 |
|
273 /** |
|
274 @defgroup auxdat Auxiliary Data Structures |
266 @defgroup auxdat Auxiliary Data Structures |
275 @ingroup datas |
267 @ingroup datas |
276 \brief Auxiliary data structures implemented in LEMON. |
268 \brief Auxiliary data structures implemented in LEMON. |
277 |
269 |
278 This group contains some data structures implemented in LEMON in |
270 This group contains some data structures implemented in LEMON in |
470 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
462 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
471 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
463 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
472 function. |
464 function. |
473 |
465 |
474 LEMON contains three algorithms for solving the minimum mean cycle problem: |
466 LEMON contains three algorithms for solving the minimum mean cycle problem: |
475 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, |
467 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, |
476 \ref dasdan98minmeancycle. |
468 \ref dasdan98minmeancycle. |
477 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved |
469 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved |
478 version of Karp's algorithm \ref dasdan98minmeancycle. |
470 version of Karp's algorithm \ref dasdan98minmeancycle. |
479 - \ref Howard "Howard"'s policy iteration algorithm |
471 - \ref HowardMmc Howard's policy iteration algorithm |
480 \ref dasdan98minmeancycle. |
472 \ref dasdan98minmeancycle. |
481 |
473 |
482 In practice, the Howard algorithm proved to be by far the most efficient |
474 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the |
483 one, though the best known theoretical bound on its running time is |
475 most efficient one, though the best known theoretical bound on its running |
484 exponential. |
476 time is exponential. |
485 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
477 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |
486 O(n<sup>2</sup>+e), but the latter one is typically faster due to the |
478 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is |
487 applied early termination scheme. |
479 typically faster due to the applied early termination scheme. |
488 */ |
480 */ |
489 |
481 |
490 /** |
482 /** |
491 @defgroup matching Matching Algorithms |
483 @defgroup matching Matching Algorithms |
492 @ingroup algs |
484 @ingroup algs |