We consider the problem of, given an undirected graph G with a nonnegative weight on each edge, finding a basis of the cycle space of G of minimum total weight, where the total weight of a basis is the sum of the weights of its cycles. Minimum cycle bases are of interest in a variety of fields. In [13] Horton proposed a first polynomial-time algorithm where a minimum cycle basis is extracted from a polynomial-size subset of candidate cycles in O(m~3n) by using Gaussian elimination. In a different approach, due to de Pina [7] and refined in [15], the cycles of a minimum cycle basis are determined sequentially in O(m~2n+mn~2 log n). A more sophisticated hybrid algorithm proposed in [18] has the best worst-case complexity of O(m~2n/log n + mn~2). In this work we revisit Horton's and de Pina's approaches and we propose a simple hybrid algorithm which improves the worst-case complexity to O(m~2n/log n). We also present a very efficient related algorithm that relies on an adaptive independence test a la de Pina. Computational results on a wide set of instances show that the latter algorithm outperforms the previous algorithms by one or two order of magnitude on medium-size instances and allows to solve instances with up to 3000 vertices in a reasonable time.
展开▼
