TY - JOUR AU - Pilarczyk, Paweł PY - 2020 TI - A space-efficient algorithm for computing the minimum cycle mean in a directed graph JO - Journal of Mathematics and Computer Science SP - 349--355 VL - 20 IS - 4 AB - 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. SN - ISSN 2008-949X UR - http://dx.doi.org/10.22436/jmcs.020.04.08 DO - 10.22436/jmcs.020.04.08 ID - Pilarczyk2020 ER - TY - BOOK TI - Network Flows: Theory, Algorithms, and Applications AU - R. K. Ahuja AU - T. L. Magnanti AU - J. B. Orlin PB - Prentice-Hall PY - 1993 DA - 1993// CY - Englewood Cliffs ID - Ahuja1993 ER - TY - BOOK TI - Introduction to algorithms AU - T. H. Cormen AU - C. E. Leiserson AU - R. L. Rivest AU - C. Stein PB - MIT Press PY - 2001 DA - 2001// CY - Cambridge ID - Cormen2001 ER - TY - JOUR TI - Faster maximum and minimum mean cycle alogrithms for system performance analysis AU - A. Dasdan AU - R. K. Gupta JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems PY - 1998 DA - 1998// VL - 17 ID - Dasdan1998 ER - TY - JOUR TI - Efficient algorithms for optimum cycle mean and optimum cost to time ration problems AU - A. Dasdan AU - S. S. Irani AU - R. K. Gupta JO - Proc. 36th Design Automation Conf. (DAC) PY - 1999 DA - 1999// VL - 1999 ID - Dasdan1999 ER - TY - JOUR TI - Quantitative hyperbolicity estimates in one-dimensional dynamics AU - S. Day AU - H. Kokubu AU - S. Luzzatto AU - K. Mischaikow AU - H. Oka AU - P. Pilarczyk JO - Nonlinearity PY - 2008 DA - 2008// VL - 21 ID - Day2008 ER - TY - BOOK TI - Minimum Mean Cycle Algorithms AU - Egerváry Research Group on Combinatorial Optimization (EGRES) PB - Library for Efficient Modeling and Optimization in Networks (LEMON) 1.2.3 Documentation PY - 2020 DA - 2020// CY - ID - (EGRES)2020 ER - TY - JOUR TI - Uniform expansivity outside a critical neighborhood in the quadratic family AU - A. Golmakani AU - S. Luzzatto AU - P. Pilarczyk JO - Exp. Math. PY - 2016 DA - 2016// VL - 25 ID - Golmakani2016 ER - TY - JOUR TI - Finding minimum cost to time ratio cycles with small integral transit times AU - M. Hartmann AU - J. B. Orlin JO - Networks PY - 1993 DA - 1993// VL - 23 ID - Hartmann1993 ER - TY - JOUR TI - A characterization of the minimum cycle mean in a digraph AU - R. M. Karp JO - Discrete Math. PY - 1978 DA - 1978// VL - 23 ID - Karp1978 ER - TY - BOOK TI - Interval Analysis AU - R. E. Moore PB - Prentice-Hall PY - 1966 DA - 1966// CY - Englewood Cliffs ID - Moore1966 ER - TY - BOOK TI - Minimum Cycle Mean Algorithms for Directed Graphs: A C++ Implementation AU - P. Pilarczyk PB - The CyMeAlg Software PY - 2020 DA - 2020// CY - ID - Pilarczyk2020 ER -