TY - GEN A1 - Liebchen, Christian A1 - Rizzi, Romeo T1 - A Greedy Approach to Compute a Minimum Cycle Bases of a Directed Graph N2 - Given a directed graph D = (V;A), we consider its cycle space CD, i.e. the vector subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An oriented cycle of D is just any cycle of the underlying undirected graph of D along with an orientation; its incidence vector is 0 on the arcs not included, while, for the included arcs, it is +1 on the arcs oriented according to the orientation and -1 on the arcs going backward. Assume a nonnegative weight wa ? R+ is associated to each arc a of D. We can extend the weighting w to subsets F of A and to families F of such subsets by dening w(F) := ?f?F w(f) and w(F) := ?F?F w(F). Given the pair (D;w), we are interested in computing a minimum weight basis of CD. This problem is strongly related to the classical problem of computing a minimum cycle basis of an undirected graph. In 1987, Horton developed the first polynomial time algorithm for computing a minimum cycle basis of an undirected graph. As for directed graphs, the first algorithm for computing a minimum directed cycle basis is due to Kavitha and Mehlhorn. Its asymptotic complexity is ~O (m4n). In this paper, we show how the original approach of Horton can be actually pursued also in the context of directed graphs, while retaining its simplicity. This both allows for a practical ~O(m4n) adaptation of Horton's original algorithm requiring only minor modifications in the actual code and for a more involved ~O(mw+1n) solution. At the end, we discuss the applicability of this approach to more specialized classes of directed cycle bases, namely, integral cycle bases and generalized fundamental cycle bases. Y1 - 2005 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/220 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-2204 ER -