New Length Bounds for Cycle Bases

Michael Elkin, Christian Liebchen, and Romeo Rizzi

Information Processing Letters 104 (5), pages 186-193, 2007

not available

Minimum cycle basis problem, tree metrics, Deo's conjecture

Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n²) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).

For weighted graphs, we construct cycle bases of length O(W log(n) log(log(n))), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Ω(W log(n)).

We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases - as it is inherent to the approach of Elkin et al. - but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998).

Download as [PDF] [ps.gz]