| Minimum Cycle Bases: Faster and Simpler (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} ({−1, 0, 1}) incidence vector is associated with each cycle and the vector space over F2 (Q) generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. There exists a set of Θ(mn) cycles which is guarantied to contain a minimum cycle basis. A minimum basis can be extracted by Gaussian elimination. The resulting algorithm [Horton 1987] was the first polynomial time algorithm. Faster and more complicated algorithms have been found since then. We present a very simple method for extracting a minimum cycle basis from the candidate set, which improves the running time for sparse graphs. Furthermore, in the undirected case by using bit-packing we improve the running time also in the case of dense graphs. Our results improve the running times of both exact and approximate algorithms. Finally, we derive a smaller candidate set with size in Ω(m) ∩ O(mn). | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||