Package com.jgalgo.alg.cycle

Class MinimumMeanCycleHoward

java.lang.Object

com.jgalgo.alg.cycle.MinimumMeanCycleAbstract

com.jgalgo.alg.cycle.MinimumMeanCycleHoward

All Implemented Interfaces:

MinimumMeanCycle

public class MinimumMeanCycleHoward
extends MinimumMeanCycleAbstract

Howard's algorithm for minimum mean cycle detection.

The algorithm runs in \(O(m N)\) and uses linear space, where \(N\) is product of the out-degrees of all the vertices in the graph. Although this bound is not polynomial, this algorithm perform well in practice. There are other bounds on the time such as \(O(n m \alpha)\) where \(\alpha\) is the number of simple cycles in the graph, or \(O(n^2 m (MaxW-MinW)/\epsilon)\) where \(MaxW,MinW\) are the maximum and minimum edge weight in the graph, and \(\epsilon\) is the precision of the algorithm.

Based on 'Efficient Algorithms for Optimal Cycle Mean and Optimum Cost to Time Ratio Problems' by Ali Dasdan, Sandy S. Irani, Rajesh K. Gupta (1999).

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
MinimumMeanCycleHoward()	Create a new minimum mean cycle algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.cycle.MinimumMeanCycleAbstract

computeMinimumMeanCycle

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MinimumMeanCycleHoward

public MinimumMeanCycleHoward()

Create a new minimum mean cycle algorithm.

Please prefer using MinimumMeanCycle.newInstance() to get a default implementation for the MinimumMeanCycle interface.