Refine
Document Type
- Doctoral thesis (1)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Year of publication
- 2014 (1)
Language
- English (1)
Keywords
- NP-completeness (1) (remove)
Institute
A cycle basis of a graph is a basis of its cycle space, the vector space which is spanned by the cycles of the graph. Practical applications for cycle bases are for example the optimization of periodic timetables, electrical engineering, and chemistry. Often, cycle bases belong to the input of algorithms concerning these fields. In these cases, the running time of the algorithm can depend on the size of the given cycle basis. In this thesis, we study the complexity of finding minimum cycle bases of several types on different graph classes. As a main result, we show that the problem of minimizing strictly fundamental cycle bases on planar graphs is NP-complete. We also give a similarly structured proof for problem of finding a maximum leaf spanning tree on the very restricted class of cubic planar graphs. Additionally, we show that this problem is APX-complete on k-regular graphs for odd k greater than 3. Furthermore, we classify types of robust cycle bases and study their relationship to fundamental cycle bases.