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 |
446 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
438 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the |
447 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
439 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length |
448 function. |
440 function. |
449 |
441 |
450 LEMON contains three algorithms for solving the minimum mean cycle problem: |
442 LEMON contains three algorithms for solving the minimum mean cycle problem: |
451 - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, |
443 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, |
452 \ref dasdan98minmeancycle. |
444 \ref dasdan98minmeancycle. |
453 - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved |
445 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved |
454 version of Karp's algorithm \ref dasdan98minmeancycle. |
446 version of Karp's algorithm \ref dasdan98minmeancycle. |
455 - \ref Howard "Howard"'s policy iteration algorithm |
447 - \ref HowardMmc Howard's policy iteration algorithm |
456 \ref dasdan98minmeancycle. |
448 \ref dasdan98minmeancycle. |
457 |
449 |
458 In practice, the Howard algorithm proved to be by far the most efficient |
450 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the |
459 one, though the best known theoretical bound on its running time is |
451 most efficient one, though the best known theoretical bound on its running |
460 exponential. |
452 time is exponential. |
461 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
453 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms |
462 O(n<sup>2</sup>+e), but the latter one is typically faster due to the |
454 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is |
463 applied early termination scheme. |
455 typically faster due to the applied early termination scheme. |
464 */ |
456 */ |
465 |
457 |
466 /** |
458 /** |
467 @defgroup matching Matching Algorithms |
459 @defgroup matching Matching Algorithms |
468 @ingroup algs |
460 @ingroup algs |