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.
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 |