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(nm). An implementation in C++ is made publicly available at http://www.pawelpilarczyk.com/cymealg/.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.22436/jmcs.020.04.08
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach
- Language
- angielski
- Publication year
- 2020
