Inhalt des Dokuments
Preprint 03-2007
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Benchmarks for Strictly Fundamental Cycle Bases
- Authors
- Publication
- published in Springer LNCS 4525 Proceedings of WEA 2007
- Classification
-
not available
- Keywords
-
strictly fundamental cycle bases, cycle bases on grids, local search, heuristics, lower and upper bounds
- Abstract
-
In the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et~al. (2004).We improve significantly their bounds, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem which will be designed only in the future.
- Source
- Download as [PDF]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe