COIN-OR::LEMON - Graph Library

Changeset 768:0a42883c8221 in lemon-1.2


Ignore:
Timestamp:
08/12/09 09:45:15 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r663 r768  
    392392
    393393/**
     394@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     395@ingroup algs
     396\brief Algorithms for finding minimum mean cycles.
     397
     398This group contains the algorithms for finding minimum mean cycles.
     399
     400The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     401of minimum mean length (cost) in a digraph.
     402The mean length of a cycle is the average length of its arcs, i.e. the
     403ratio between the total length of the cycle and the number of arcs on it.
     404
     405This problem has an important connection to \e conservative \e length
     406\e functions, too. A length function on the arcs of a digraph is called
     407conservative if and only if there is no directed cycle of negative total
     408length. For an arbitrary length function, the negative of the minimum
     409cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     410arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     411function.
     412
     413LEMON contains three algorithms for solving the minimum mean cycle problem:
     414- \ref Karp "Karp"'s original algorithm.
     415- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     416  version of Karp's algorithm.
     417- \ref Howard "Howard"'s policy iteration algorithm.
     418
     419In practice, the Howard algorithm proved to be by far the most efficient
     420one, though the best known theoretical bound on its running time is
     421exponential.
     422Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     423O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     424applied early termination scheme.
     425*/
     426
     427/**
    394428@defgroup graph_properties Connectivity and Other Graph Properties
    395429@ingroup algs
  • lemon/hartmann_orlin.h

    r767 r768  
    2020#define LEMON_HARTMANN_ORLIN_H
    2121
    22 /// \ingroup shortest_path
     22/// \ingroup min_mean_cycle
    2323///
    2424/// \file
     
    9191
    9292
    93   /// \addtogroup shortest_path
     93  /// \addtogroup min_mean_cycle
    9494  /// @{
    9595
     
    9999  /// This class implements the Hartmann-Orlin algorithm for finding
    100100  /// a directed cycle of minimum mean length (cost) in a digraph.
    101   /// It is an improved version of \ref Karp "Karp's original algorithm",
     101  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
    102102  /// it applies an efficient early termination scheme.
     103  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    103104  ///
    104105  /// \tparam GR The type of the digraph the algorithm runs on.
  • lemon/howard.h

    r767 r768  
    2020#define LEMON_HOWARD_H
    2121
    22 /// \ingroup shortest_path
     22/// \ingroup min_mean_cycle
    2323///
    2424/// \file
     
    9191
    9292
    93   /// \addtogroup shortest_path
     93  /// \addtogroup min_mean_cycle
    9494  /// @{
    9595
     
    9999  /// This class implements Howard's policy iteration algorithm for finding
    100100  /// a directed cycle of minimum mean length (cost) in a digraph.
     101  /// This class provides the most efficient algorithm for the
     102  /// minimum mean cycle problem, though the best known theoretical
     103  /// bound on its running time is exponential.
    101104  ///
    102105  /// \tparam GR The type of the digraph the algorithm runs on.
  • lemon/karp.h

    r767 r768  
    2020#define LEMON_KARP_H
    2121
    22 /// \ingroup shortest_path
     22/// \ingroup min_mean_cycle
    2323///
    2424/// \file
     
    9191
    9292
    93   /// \addtogroup shortest_path
     93  /// \addtogroup min_mean_cycle
    9494  /// @{
    9595
     
    9999  /// This class implements Karp's algorithm for finding a directed
    100100  /// cycle of minimum mean length (cost) in a digraph.
     101  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    101102  ///
    102103  /// \tparam GR The type of the digraph the algorithm runs on.
Note: See TracChangeset for help on using the changeset viewer.