doc/groups.dox
changeset 894 24b3f18ed9e2
parent 877 141f9c0db4a3
child 904 c279b19abc62
equal deleted inserted replaced
45:021a0a5b20a5 46:ac80c6ede998
   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