Changeset 818:8452ca46e29a in lemon

Timestamp:

10/15/09 12:55:41 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Add citations to the min mean cycle classes (#179, #184)

Files:

• doc/groups.dox (modified) (2 diffs)
• lemon/hartmann_orlin.h (modified) (1 diff)
• lemon/howard.h (modified) (1 diff)
• lemon/karp.h (modified) (1 diff)

doc/groups.dox

@@ -458 +458 @@
 \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
@@ -474 +475 @@
 
 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

lemon/hartmann_orlin.h

@@ -98 +98 @@
   ///
   /// 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.

lemon/howard.h

@@ -98 +98 @@
   ///
   /// 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

lemon/karp.h

@@ -98 +98 @@
   ///
   /// 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(n<sup>2</sup>+e).
   ///