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

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 1281 Downloads
• 2642 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

Keywords

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

MSC

•  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)
  • Google Scholar


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


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • Google Scholar


• [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
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [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)
  • View Article


• [7] A. Golmakani, S. Luzzatto, P. Pilarczyk, Uniform expansivity outside a critical neighborhood in the quadratic family, Exp. Math., 25 (2016), 116--124
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


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


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


• [10] R. E. Moore, Interval Analysis, Prentice-Hall, Englewood Cliffs (1966)
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


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