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^3 n) 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^2 n + m n^2 logn). A more sophisticated hybrid algorithm proposed in [18] has the best worst-case complexity of O(m^2 n / log n + m n^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^2 n / logn). We also present a very efficient related algorithm that relies on an adaptive independence test à 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.
Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs.
RIZZI, ROMEO
2010-01-01
Abstract
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^3 n) 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^2 n + m n^2 logn). A more sophisticated hybrid algorithm proposed in [18] has the best worst-case complexity of O(m^2 n / log n + m n^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^2 n / logn). We also present a very efficient related algorithm that relies on an adaptive independence test à 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
