Theses offered at the chair

Many problems, such as the Travelling Salesperson Problem, or the Graph Colouring Problem, are computationally hard in general. However, they lie at the core of numerous practical applications, so they need to be solved nevertheless. Most thesis topics at this chair are motivated by such a hard problem.

Furthermore, we are interested in providing performance guarantees, e.g. regarding accuracy of the computed answer, running time, or energy consumption.

A variety of topics are offered, from areas such as:

• graph algorithms
• (parameterised) complexity theory
• cops and robber games
• graph decompositions (tree decompositions)
• logic and algorithms
• model checking
• highly efficient algorithms with guarantees (property testing)
• logic puzzles and SAT/constraint solving
• graph structure theory.

Topics related to our existing implementations of tree decompositions, and property testing algorithms are available.

If you would like to write your BSc thesis or MSc thesis at this chair, you should normally have successfully completed at least one module at the chair (excluding Inf-DM-B), followed by a seminar or a project.

Both purely theoretical topics and topics combining theory and implementation are available.

Purely theoretical topics are only available to students with a proven strong background in theoretical/mathematical subjects.

If you are interested in a topic, please arrange an appointment with Isolde Adler by emailing Stefanie Dettmer (secretary) on algok(at)uni-bamberg.de.