TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2006

COGA 5-Wheel


zur Navigation

Preprints 2006

A New Bound on the Length of Minimum Cycle Bases
Zitatschlüssel Report-032-2006
Autor Romeo Rizzi and Christian Liebchen
Jahr 2006
Adresse Strasse des 17. Juni 136, 10623 Berlin
Nummer 032
Monat December
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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 Ømega(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).
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe