Benchmarks for Strictly Fundamental Cycle Bases
Please always quote using this URN:urn:nbn:de:0296-matheon-4065
- 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.
Author: | Christian Liebchen, Gregor Wünsch, Ekkehard Köhler, Alexander Reiche, Romeo Rizzi |
---|---|
URN: | urn:nbn:de:0296-matheon-4065 |
Referee: | Rolf H. Möhring |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2008/02/21 |
Release Date: | 2008/02/21 |
Institute: | Technische Universität Berlin |
Zuse Institute Berlin (ZIB) | |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C05 Trees |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
Preprint Number: | 455 |