• search hit 10 of 12
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.