TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2004

COGA 5-Wheel

Page Content

to Navigation

Preprints 2004

A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph
Citation key Report-031-2004
Author Christian Liebchen and Romeo Rizzi
Year 2004
Number 031
Note A condensed version appeared in Information Processing Letters 94 (3), pages 107-112, Elsevier
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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^4 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^ømega n)$, in particular $O(m^3.376 n)$. Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe