# A space-efficient algorithm for computing the minimum cycle mean in a directed graph

Volume 20, Issue 4, pp 349--355
Publication Date: March 06, 2020 Submission Date: August 24, 2019 Revision Date: January 23, 2020 Accteptance Date: February 01, 2020
• 108 Views

### Authors

Paweł Pilarczyk - Gdańsk University of Technology, ul. , Narutowicza 11/12, 80-233 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 space-efficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349--355

##### AMA Style

Pilarczyk Paweł, A space-efficient algorithm for computing the minimum cycle mean in a directed graph. J Math Comput SCI-JM. (2020); 20(4):349--355

##### Chicago/Turabian Style

Pilarczyk, Paweł. "A space-efficient algorithm for computing the minimum cycle mean in a directed graph." Journal of Mathematics and Computer Science, 20, no. 4 (2020): 349--355

### Keywords

• Directed graph
• weighted graph
• sparse graph
• algorithm
• minimum cycle mean
• mean cycle weight
• rigorous numerics
• floating-point arithmetic
• rounding

•  05C20
•  05C22
•  05C38

### References

• [1] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 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 Computer-Aided Design of Integrated Circuits and Systems, 17 (1998), 889--899

• [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), 37--42

• [5] S. Day, H. Kokubu, S. Luzzatto, K. Mischaikow, H. Oka, P. Pilarczyk, Quantitative hyperbolicity estimates in one-dimensional dynamics, Nonlinearity, 21 (2008), 1967--1987

• [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), 116--124

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

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

• [10] R. E. Moore, Interval Analysis, Prentice-Hall, Englewood Cliffs (1966)

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