author Peter Kovacs Thu, 15 Oct 2009 12:55:41 +0200 changeset 818 8452ca46e29a parent 817 432c54cec63c child 819 f964a00b9068
Add citations to the min mean cycle classes (#179, #184)
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/hartmann_orlin.h file | annotate | diff | comparison | revisions lemon/howard.h file | annotate | diff | comparison | revisions lemon/karp.h file | annotate | diff | comparison | revisions
     1.1 --- a/doc/groups.dox	Thu Nov 05 08:39:49 2009 +0100
1.2 +++ b/doc/groups.dox	Thu Oct 15 12:55:41 2009 +0200
1.3 @@ -457,7 +457,8 @@
1.4  @ingroup algs
1.5  \brief Algorithms for finding minimum mean cycles.
1.6
1.7 -This group contains the algorithms for finding minimum mean cycles.
1.8 +This group contains the algorithms for finding minimum mean cycles
1.9 +\ref clrs01algorithms, \ref amo93networkflows.
1.10
1.11  The \e minimum \e mean \e cycle \e problem is to find a directed cycle
1.12  of minimum mean length (cost) in a digraph.
1.13 @@ -473,10 +474,12 @@
1.14  function.
1.15
1.16  LEMON contains three algorithms for solving the minimum mean cycle problem:
1.17 -- \ref Karp "Karp"'s original algorithm.
1.18 +- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
1.19 +  \ref dasdan98minmeancycle.
1.20  - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
1.21 -  version of Karp's algorithm.
1.22 -- \ref Howard "Howard"'s policy iteration algorithm.
1.23 +  version of Karp's algorithm \ref dasdan98minmeancycle.
1.24 +- \ref Howard "Howard"'s policy iteration algorithm
1.25 +  \ref dasdan98minmeancycle.
1.26
1.27  In practice, the Howard algorithm proved to be by far the most efficient
1.28  one, though the best known theoretical bound on its running time is

     2.1 --- a/lemon/hartmann_orlin.h	Thu Nov 05 08:39:49 2009 +0100
2.2 +++ b/lemon/hartmann_orlin.h	Thu Oct 15 12:55:41 2009 +0200
2.3 @@ -97,7 +97,8 @@
2.4    /// a minimum mean cycle.
2.5    ///
2.6    /// This class implements the Hartmann-Orlin algorithm for finding
2.7 -  /// a directed cycle of minimum mean length (cost) in a digraph.
2.8 +  /// a directed cycle of minimum mean length (cost) in a digraph
2.9 +  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
2.10    /// It is an improved version of \ref Karp "Karp"'s original algorithm,
2.11    /// it applies an efficient early termination scheme.
2.12    /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).

     3.1 --- a/lemon/howard.h	Thu Nov 05 08:39:49 2009 +0100
3.2 +++ b/lemon/howard.h	Thu Oct 15 12:55:41 2009 +0200
3.3 @@ -97,7 +97,8 @@
3.4    /// mean cycle.
3.5    ///
3.6    /// This class implements Howard's policy iteration algorithm for finding
3.7 -  /// a directed cycle of minimum mean length (cost) in a digraph.
3.8 +  /// a directed cycle of minimum mean length (cost) in a digraph
3.9 +  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
3.10    /// This class provides the most efficient algorithm for the
3.11    /// minimum mean cycle problem, though the best known theoretical
3.12    /// bound on its running time is exponential.

     4.1 --- a/lemon/karp.h	Thu Nov 05 08:39:49 2009 +0100
4.2 +++ b/lemon/karp.h	Thu Oct 15 12:55:41 2009 +0200
4.3 @@ -97,7 +97,8 @@
4.4    /// mean cycle.
4.5    ///
4.6    /// This class implements Karp's algorithm for finding a directed
4.7 -  /// cycle of minimum mean length (cost) in a digraph.
4.8 +  /// cycle of minimum mean length (cost) in a digraph
4.9 +  /// \ref amo93networkflows, \ref dasdan98minmeancycle.
4.10    /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
4.11    ///
4.12    /// \tparam GR The type of the digraph the algorithm runs on.