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

Search

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

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

seen 3 times

Recommended for you

Meta Tags