# Changeset 768:0a42883c8221 in lemon-1.2

Ignore:
Timestamp:
08/12/09 09:45:15 (10 years ago)
Branch:
default
Phase:
public
Message:

Separate group for the min mean cycle classes (#179)

Files:
4 edited

Unmodified
Added
Removed
• ## doc/groups.dox

 r663 /** @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
• ## lemon/hartmann_orlin.h

 r767 #define LEMON_HARTMANN_ORLIN_H /// \ingroup shortest_path /// \ingroup min_mean_cycle /// /// \file /// \addtogroup shortest_path /// \addtogroup min_mean_cycle /// @{ /// 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.
• ## lemon/howard.h

 r767 #define LEMON_HOWARD_H /// \ingroup shortest_path /// \ingroup min_mean_cycle /// /// \file /// \addtogroup shortest_path /// \addtogroup min_mean_cycle /// @{ /// 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.
• ## lemon/karp.h

 r767 #define LEMON_KARP_H /// \ingroup shortest_path /// \ingroup min_mean_cycle /// /// \file /// \addtogroup shortest_path /// \addtogroup min_mean_cycle /// @{ /// 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.
Note: See TracChangeset for help on using the changeset viewer.