Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 663)
+++ doc/groups.dox (revision 768)
@@ -392,4 +392,38 @@
/**
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref Karp "Karp"'s original algorithm.
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+ version of Karp's algorithm.
+- \ref Howard "Howard"'s policy iteration algorithm.
+
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
+O(n^{2}+e), but the latter one is typically faster due to the
+applied early termination scheme.
+*/
+
+/**
@defgroup graph_properties Connectivity and Other Graph Properties
@ingroup algs
Index: lemon/hartmann_orlin.h
===================================================================
--- lemon/hartmann_orlin.h (revision 767)
+++ lemon/hartmann_orlin.h (revision 768)
@@ -20,5 +20,5 @@
#define LEMON_HARTMANN_ORLIN_H
-/// \ingroup shortest_path
+/// \ingroup min_mean_cycle
///
/// \file
@@ -91,5 +91,5 @@
- /// \addtogroup shortest_path
+ /// \addtogroup min_mean_cycle
/// @{
@@ -99,6 +99,7 @@
/// This class implements the Hartmann-Orlin algorithm for finding
/// a directed cycle of minimum mean length (cost) in a digraph.
- /// It is an improved version of \ref Karp "Karp's original algorithm",
+ /// It is an improved version of \ref Karp "Karp"'s original algorithm,
/// it applies an efficient early termination scheme.
+ /// It runs in time O(ne) and uses space O(n^{2}+e).
///
/// \tparam GR The type of the digraph the algorithm runs on.
Index: lemon/howard.h
===================================================================
--- lemon/howard.h (revision 767)
+++ lemon/howard.h (revision 768)
@@ -20,5 +20,5 @@
#define LEMON_HOWARD_H
-/// \ingroup shortest_path
+/// \ingroup min_mean_cycle
///
/// \file
@@ -91,5 +91,5 @@
- /// \addtogroup shortest_path
+ /// \addtogroup min_mean_cycle
/// @{
@@ -99,4 +99,7 @@
/// This class implements Howard's policy iteration algorithm for finding
/// a directed cycle of minimum mean length (cost) in a digraph.
+ /// This class provides the most efficient algorithm for the
+ /// minimum mean cycle problem, though the best known theoretical
+ /// bound on its running time is exponential.
///
/// \tparam GR The type of the digraph the algorithm runs on.
Index: lemon/karp.h
===================================================================
--- lemon/karp.h (revision 767)
+++ lemon/karp.h (revision 768)
@@ -20,5 +20,5 @@
#define LEMON_KARP_H
-/// \ingroup shortest_path
+/// \ingroup min_mean_cycle
///
/// \file
@@ -91,5 +91,5 @@
- /// \addtogroup shortest_path
+ /// \addtogroup min_mean_cycle
/// @{
@@ -99,4 +99,5 @@
/// This class implements Karp's algorithm for finding a directed
/// cycle of minimum mean length (cost) in a digraph.
+ /// It runs in time O(ne) and uses space O(n^{2}+e).
///
/// \tparam GR The type of the digraph the algorithm runs on.