Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length 0(n(2)) 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 Q (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).

New length bounds for cycle bases

RIZZI, ROMEO
2007

Abstract

Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length 0(n(2)) 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 Q (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).
Cycle bases; Metric approximation
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/409542
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 12
social impact