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(nm). An implementation in C++ is made publicly available at http://www.pawelpilarczyk.com/cymealg/.
Citations

0
CrossRef

0
Web of Science

0
Scopus
Author
Keywords
Details
 Category:
 Articles
 Type:
 artykuły w czasopismach
 Published in:

Journal of Mathematics and Computer ScienceJMCS
no. 20,
pages 349  355,
ISSN: 2008949X  Language:
 English
 Publication year:
 2020
 Bibliographic description:
 Pilarczyk P.: A spaceefficient algorithm for computing the minimum cycle mean in a directed graph// Journal of Mathematics and Computer ScienceJMCS Vol. 20,iss. 4 (2020), s.349355
 DOI:
 Digital Object Identifier (open in new tab) 10.22436/jmcs.020.04.08
 Verified by:
 Gdańsk University of Technology
seen 3 times