A spaceefficient algorithm for computing the minimum cycle mean in a directed graph
Volume 20, Issue 4, pp 349355
http://dx.doi.org/10.22436/jmcs.020.04.08
Publication Date: March 06, 2020
Submission Date: August 24, 2019
Revision Date: January 23, 2020
Accteptance Date: February 01, 2020
Authors
Paweł Pilarczyk
 Gdańsk University of Technology, ul. , Narutowicza 11/12, 80233 Gdańsk, Poland.
Abstract
An algorithm is introduced for computing the minimum cycle mean
in a strongly connected directed graph with \(n\) vertices and \(m\) arcs
that requires \(O (n)\) working space.
This is a considerable improvement for sparse graphs
in comparison to the classical algorithms
that require \(O (n^2)\) working space.
The time complexity of the algorithm is still \(O (n m)\).
An implementation in C++ is made publicly available
at
http://www.pawelpilarczyk.com/cymealg.
Share and Cite
ISRP Style
Paweł Pilarczyk, A spaceefficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349355
AMA Style
Pilarczyk Paweł, A spaceefficient algorithm for computing the minimum cycle mean in a directed graph. J Math Comput SCIJM. (2020); 20(4):349355
Chicago/Turabian Style
Pilarczyk, Paweł. "A spaceefficient algorithm for computing the minimum cycle mean in a directed graph." Journal of Mathematics and Computer Science, 20, no. 4 (2020): 349355
Keywords
 Directed graph
 weighted graph
 sparse graph
 algorithm
 minimum cycle mean
 mean cycle weight
 rigorous numerics
 floatingpoint arithmetic
 rounding
MSC
References

[1]
R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, PrenticeHall, Englewood Cliffs (1993)

[2]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT Press, Cambridge (2001)

[3]
A. Dasdan, R. K. Gupta, Faster maximum and minimum mean cycle alogrithms for system performance analysis, IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 17 (1998), 889899

[4]
A. Dasdan, S. S. Irani, R. K. Gupta, Efficient algorithms for optimum cycle mean and optimum cost to time ration problems, Proc. 36th Design Automation Conf. (DAC), 1999 (1999), 3742

[5]
S. Day, H. Kokubu, S. Luzzatto, K. Mischaikow, H. Oka, P. Pilarczyk, Quantitative hyperbolicity estimates in onedimensional dynamics, Nonlinearity, 21 (2008), 19671987

[6]
Egerváry Research Group on Combinatorial Optimization (EGRES), Minimum Mean Cycle Algorithms, Library for Efficient Modeling and Optimization in Networks (LEMON) 1.2.3 Documentation, (2020)

[7]
A. Golmakani, S. Luzzatto, P. Pilarczyk, Uniform expansivity outside a critical neighborhood in the quadratic family, Exp. Math., 25 (2016), 116124

[8]
M. Hartmann, J. B. Orlin, Finding minimum cost to time ratio cycles with small integral transit times, Networks, 23 (1993), 567574

[9]
R. M. Karp, A characterization of the minimum cycle mean in a digraph, Discrete Math., 23 (1978), 309311

[10]
R. E. Moore, Interval Analysis, PrenticeHall, Englewood Cliffs (1966)

[11]
P. Pilarczyk, Minimum Cycle Mean Algorithms for Directed Graphs: A C++ Implementation, The CyMeAlg Software, (2020)