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 -