New length bounds for cycle bases |
| |
Authors: | Michael Elkin Romeo Rizzi |
| |
Affiliation: | a Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel b Technische Universität Berlin, Institut für Mathematik, Combinatorial Optimization and Graph Algorithms, Straße des 17. Juni 136, D-10623 Berlin, Germany c DIMI, Università di Udine, Italy |
| |
Abstract: | 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⋅lognloglogn), 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⋅logn).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). |
| |
Keywords: | Graph algorithms Approximation algorithms Cycle bases Metric approximation |
本文献已被 ScienceDirect 等数据库收录! |
|