doc/groups.dox
changeset 769 e746fb14e680
parent 663 8b0df68370a4
child 770 432c54cec63c
equal deleted inserted replaced
29:44bea10dbfb9 37:da1254bbf7ec
   389 If you want to find minimum cut just between two distinict nodes,
   389 If you want to find minimum cut just between two distinict nodes,
   390 see the \ref max_flow "maximum flow problem".
   390 see the \ref max_flow "maximum flow problem".
   391 */
   391 */
   392 
   392 
   393 /**
   393 /**
       
   394 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms
       
   395 @ingroup algs
       
   396 \brief Algorithms for finding minimum mean cycles.
       
   397 
       
   398 This group contains the algorithms for finding minimum mean cycles.
       
   399 
       
   400 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
       
   401 of minimum mean length (cost) in a digraph.
       
   402 The mean length of a cycle is the average length of its arcs, i.e. the
       
   403 ratio between the total length of the cycle and the number of arcs on it.
       
   404 
       
   405 This 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
       
   407 conservative if and only if there is no directed cycle of negative total
       
   408 length. For an arbitrary length function, the negative of the minimum
       
   409 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
       
   410 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
       
   411 function.
       
   412 
       
   413 LEMON 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 
       
   419 In practice, the Howard algorithm proved to be by far the most efficient
       
   420 one, though the best known theoretical bound on its running time is
       
   421 exponential.
       
   422 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
       
   423 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
       
   424 applied early termination scheme.
       
   425 */
       
   426 
       
   427 /**
   394 @defgroup graph_properties Connectivity and Other Graph Properties
   428 @defgroup graph_properties Connectivity and Other Graph Properties
   395 @ingroup algs
   429 @ingroup algs
   396 \brief Algorithms for discovering the graph properties
   430 \brief Algorithms for discovering the graph properties
   397 
   431 
   398 This group contains the algorithms for discovering the graph properties
   432 This group contains the algorithms for discovering the graph properties