direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 22-2007

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

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(n2) 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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe