| 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 |
