A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph

Christian Liebchen and Romeo Rizzi

A condensed version appeared in Information Processing Letters 94 (3), pages 107-112, Elsevier

cycle bases, directed graphs, greedy algorithm

We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton and hereby obtain a very simple exact algorithm of complexity O(m⁴ n), being as fast as the first algorithm proposed for this problem. Moreover, the speed-up of Golynski and Horton applies to this problem, providing an exact algorithm of complexity O(m^ω n), in particular O(m^3.376 n). Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.

Created on October 19 2004 | Last modified on January 20 2005

Download as [PDF] [ps.gz]