A space-efficient algorithm for computing the minimum cycle mean in a directed graph

Paweł Pilarczyk

doi:10.22436/jmcs.020.04.08

A space-efficient algorithm for computing the minimum cycle mean in a directed graph

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 (1)

Paweł Pilarczyk dr hab.

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach
Published in:: Journal of Mathematics and Computer Science-JMCS no. 20, pages 349 - 355,
ISSN: 2008-949X
Language:: English
Publication year:: 2020
Bibliographic description:: Pilarczyk P.: A space-efficient algorithm for computing the minimum cycle mean in a directed graph// Journal of Mathematics and Computer Science-JMCS -Vol. 20,iss. 4 (2020), s.349-355
DOI:: Digital Object Identifier (open in new tab) 10.22436/jmcs.020.04.08
Verified by:: Gdańsk University of Technology