direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 32-2006

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

A New Bound on the Length of Minimum Cycle Bases
primary: 05C38 Paths and cycles
secondary: 68R10 Graph theory
Combinatorial optimization, Minimum cycle basis problem, weakly fundamental cycle bases, tree metrics
For any weighted graph we construct a cycle basis 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 was obtained only recently by Elkin et al. (2005) by a logarithmic factor. From below, our result has to be compared with Ω(W*log(n)), being the length of the minimum cycle bases (MCB) of a class of graphs with large girth.
We achieve this bound 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 can take profit of some nice properties of Hierarchically Partitioned Metrics (HPM) as they have been introduced by Bartal (1998).
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe