A space-efficient algorithm for computing the minimum cycle mean in a directed graph
Paweł Pilarczyk · Journal of Mathematics and Computer Science · 2020
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.