diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -457,7 +457,8 @@ @ingroup algs \brief Algorithms for finding minimum mean cycles. -This group contains the algorithms for finding minimum mean cycles. +This group contains the algorithms for finding minimum mean cycles +\ref clrs01algorithms, \ref amo93networkflows. The \e minimum \e mean \e cycle \e problem is to find a directed cycle of minimum mean length (cost) in a digraph. @@ -473,10 +474,12 @@ function. LEMON contains three algorithms for solving the minimum mean cycle problem: -- \ref Karp "Karp"'s original algorithm. +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows, + \ref dasdan98minmeancycle. - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved - version of Karp's algorithm. -- \ref Howard "Howard"'s policy iteration algorithm. + version of Karp's algorithm \ref dasdan98minmeancycle. +- \ref Howard "Howard"'s policy iteration algorithm + \ref dasdan98minmeancycle. 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 diff --git a/lemon/hartmann_orlin.h b/lemon/hartmann_orlin.h --- a/lemon/hartmann_orlin.h +++ b/lemon/hartmann_orlin.h @@ -97,7 +97,8 @@ /// a minimum mean cycle. /// /// This class implements the Hartmann-Orlin algorithm for finding - /// a directed cycle of minimum mean length (cost) in a digraph. + /// a directed cycle of minimum mean length (cost) in a digraph + /// \ref amo93networkflows, \ref dasdan98minmeancycle. /// 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). diff --git a/lemon/howard.h b/lemon/howard.h --- a/lemon/howard.h +++ b/lemon/howard.h @@ -97,7 +97,8 @@ /// mean cycle. /// /// This class implements Howard's policy iteration algorithm for finding - /// a directed cycle of minimum mean length (cost) in a digraph. + /// a directed cycle of minimum mean length (cost) in a digraph + /// \ref amo93networkflows, \ref dasdan98minmeancycle. /// 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. diff --git a/lemon/karp.h b/lemon/karp.h --- a/lemon/karp.h +++ b/lemon/karp.h @@ -97,7 +97,8 @@ /// mean cycle. /// /// This class implements Karp's algorithm for finding a directed - /// cycle of minimum mean length (cost) in a digraph. + /// cycle of minimum mean length (cost) in a digraph + /// \ref amo93networkflows, \ref dasdan98minmeancycle. /// It runs in time O(ne) and uses space O(n2+e). /// /// \tparam GR The type of the digraph the algorithm runs on.