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

Abstrakt

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/.

Cytowania

0

CrossRef
0

Web of Science
0

Scopus

Autor (1)

Paweł Pilarczyk dr hab.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuły w czasopismach
Opublikowano w:: Journal of Mathematics and Computer Science-JMCS nr 20, strony 349 - 355,
ISSN: 2008-949X
Język:: angielski
Rok wydania:: 2020
Opis bibliograficzny:: 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:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.22436/jmcs.020.04.08
Weryfikacja:: Politechnika Gdańska