• search hit 8 of 10
Back to Result List

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

Please always quote using this URN:urn:nbn:de:0296-matheon-2204
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christian Liebchen, Romeo Rizzi
URN:urn:nbn:de:0296-matheon-2204
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/07/03
Release Date:2005/03/02
Institute:Technische Universität Berlin
Preprint Number:223
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.