All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Files
Minimum Mean Cycle Algorithms
Algorithms

Detailed Description

This group contains the algorithms for finding minimum mean cycles [1], [21].

The minimum mean cycle 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 conservative length 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 \(\epsilon\) value so that increasing the arc lengths uniformly by \(\epsilon\) results in a conservative length function.

LEMON contains three algorithms for solving the minimum mean cycle problem:

In practice, the Howard algorithm turned out to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. Both Karp and Hartmann-Orlin algorithms run in time O(nm) and use space O(n2+m).

Classes

class  HartmannOrlinMmc< GR, CM, TR >
 Implementation of the Hartmann-Orlin algorithm for finding a minimum mean cycle. More...
 
class  HowardMmc< GR, CM, TR >
 Implementation of Howard's algorithm for finding a minimum mean cycle. More...
 
class  KarpMmc< GR, CM, TR >
 Implementation of Karp's algorithm for finding a minimum mean cycle. More...
 
struct  HartmannOrlinMmc< GR, CM, TR >::SetLargeCost< T >
 Named parameter for setting LargeCost type. More...
 
struct  HartmannOrlinMmc< GR, CM, TR >::SetPath< T >
 Named parameter for setting Path type. More...
 
struct  HowardMmc< GR, CM, TR >::SetLargeCost< T >
 Named parameter for setting LargeCost type. More...
 
struct  HowardMmc< GR, CM, TR >::SetPath< T >
 Named parameter for setting Path type. More...
 
struct  KarpMmc< GR, CM, TR >::SetLargeCost< T >
 Named parameter for setting LargeCost type. More...
 
struct  KarpMmc< GR, CM, TR >::SetPath< T >
 Named parameter for setting Path type. More...
 

Files

file  hartmann_orlin_mmc.h
 Hartmann-Orlin's algorithm for finding a minimum mean cycle.
 
file  howard_mmc.h
 Howard's algorithm for finding a minimum mean cycle.
 
file  karp_mmc.h
 Karp's algorithm for finding a minimum mean cycle.