1.1 --- a/doc/groups.dox Tue Aug 11 22:52:35 2009 +0200
1.2 +++ b/doc/groups.dox Wed Aug 12 09:45:15 2009 +0200
1.3 @@ -391,6 +391,40 @@
1.4 */
1.5
1.6 /**
1.7 +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
1.8 +@ingroup algs
1.9 +\brief Algorithms for finding minimum mean cycles.
1.10 +
1.11 +This group contains the algorithms for finding minimum mean cycles.
1.12 +
1.13 +The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.14 +of minimum mean length (cost) in a digraph.
1.15 +The mean length of a cycle is the average length of its arcs, i.e. the
1.16 +ratio between the total length of the cycle and the number of arcs on it.
1.17 +
1.18 +This problem has an important connection to \e conservative \e length
1.19 +\e functions, too. A length function on the arcs of a digraph is called
1.20 +conservative if and only if there is no directed cycle of negative total
1.21 +length. For an arbitrary length function, the negative of the minimum
1.22 +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
1.23 +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
1.24 +function.
1.25 +
1.26 +LEMON contains three algorithms for solving the minimum mean cycle problem:
1.27 +- \ref Karp "Karp"'s original algorithm.
1.28 +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
1.29 + version of Karp's algorithm.
1.30 +- \ref Howard "Howard"'s policy iteration algorithm.
1.31 +
1.32 +In practice, the Howard algorithm proved to be by far the most efficient
1.33 +one, though the best known theoretical bound on its running time is
1.34 +exponential.
1.35 +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
1.36 +O(n<sup>2</sup>+e), but the latter one is typically faster due to the
1.37 +applied early termination scheme.
1.38 +*/
1.39 +
1.40 +/**
1.41 @defgroup graph_properties Connectivity and Other Graph Properties
1.42 @ingroup algs
1.43 \brief Algorithms for discovering the graph properties