Publications

Authors:

E., Köhler; C., Liebchen; G., Wünsch; Rizzi, Romeo

Title:

Lower bounds for strictly fundamental cycle bases in grid graphs.

Year:

2009

Type of item:

Articolo in Rivista

Tipologia ANVUR:

Articolo su rivista

Language:

Inglese

Format:

A Stampa

Referee:

Sì

Name of journal:

NETWORKS

ISSN of journal:

0028-3045

N° Volume:

53

Number or Folder:

2

Page numbers:

191-205

Keyword:

combinatorial optimization; minimum cycle basis; planar dual; spanning tree; asymptotic analysis

Short description of contents:

Consider the following problem: compute a spanning tree such that the sum of the lengths of its induced fundamental circuits is as small as possible. We motivate why planar square grid graphs are very relevant instances for this problem. In particular, other contributions already showed that the identification of strong lower bounds is highly challenging. Asymptotically, for a graph on n vertices, Alon et al. [SIAM J Comput 24(1995), 78–100] obtained a lower bound of Ω(n log n). We raise the n log n coefficient by a factor of 325. Concerning optimality proofs, the largest grid for which provably optimum solutions were known is 6 × 6, and it was obtained by massive MIP computing power. Here, we present a combinatorial optimality proof even for the 8 × 8 grid. These two results are complemented by new combinatorial lower bounds for the dimensions in which earlier empirical computations were performed, i.e., for up to 10,000 vertices.

Product ID:

71474

Handle IRIS:

11562/409559

Deposited On:

July 15, 2012

Last Modified:

November 17, 2022

Bibliographic citation:

E., Köhler; C., Liebchen; G., Wünsch; Rizzi, Romeo, Lower bounds for strictly fundamental cycle bases in grid graphs. «NETWORKS» , vol. 53 , n. 2 , 2009 , pp. 191-205

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo