TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2005

COGA 5-Wheel


zur Navigation

Preprints 2005

Classes of Cycle Bases
Zitatschlüssel Report-018-2005
Autor Christian Liebchen and Romeo Rizzi
Jahr 2005
Adresse Straße des 17. Juni 136, 10623 Berlin
Nummer 018
Monat August
Notiz Discrete Applied Mathematics 155 (3), pages 337-355, 2007
Institution TU Berlin
Zusammenfassung In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle basis have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiries. At present, the complexity status of the MCB problem has been settled only for undirected, directed, and strictly fundamental cycle basis. In this paper, we offer an unitary classification accommodating these 3 classes and further including the following 4 relevant classes: 2-bases (or planar bases), weakly fundamental cycle bases, totally unimodular cycle bases, and integral cycle bases. The classification is complete in that, for each ordered pair (A,B) of classes considered, we either prove that A is a subset of B for every graph or provide a counterexample graph for which A is not a subset of B. The seven notions of cycle bases are distinct (either A is not a subset of B or B is not a subset of A is exhibited for each pair (A,B). All counterexamples proposed have been designed to be ultimately effective in separating the various algorithmic variants of the MCB problem naturally associated to each one of these seven classes. We even provide a linear time algorithm for computing a minimum 2-basis of a graph. Finally, notice that the resolution of the complexity status of some of the remaining three classes would have an immediate impact on practical applications, as for instance in periodic railway timetabling, only integral cycle bases are of direct use.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe