Inhalt des Dokuments
Preprint 31-2004
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph
- Authors
- Publication
- A condensed version appeared in Information Processing Letters 94 (3), pages 107-112, Elsevier
- Classification
-
MSC: primary: 05C38 Paths and cycles - Keywords
-
cycle bases, directed graphs, greedy algorithm
- 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(m4 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(m3.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
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe