A space-efficient algorithm for computing the minimum cycle mean in a directed graph
Volume 20, Issue 4, pp 349--355
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
-
1575
Downloads
-
3458
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
MSC
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)