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(n2+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(n2+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(n2+e). /// /// \tparam GR The type of the digraph the algorithm runs on.