The main objective of the course is to derive fundamental basics for several algorithms and the algorithms themselves. Additionally, these basics imply the polynomial runtime of the mentioned algorithms. Applications for the derived algorithms can be found in operations research and biomathematics. A further objective of this course is to get familiar with several research directions which can be deepened in
a diploma thesis or even a PhD thesis.

The lecture discusses algorithmic aspects in graph theory from a theoretical point of view (Implementation issues are not covered here).

An essential topic in this lecture are different types of edge-covering walks in graphs. Eulerian trails including each edge in the graph exactly once are only a special case here. However, many types of edge-covering walks are based on Eulerian trails in more general graphs. This holds especially for the Chinese Postman Problem and walks through mazes (where only local node information is available).

Thus, the structure of the lecture is the following:

• characterization of Eulerian graphs
• Menger's theorem and the splitting lemma, node splittings, spanning trees in undirected and directed graphs (this part discusses several basics needed for proving the correctness of some polynomial time algorithms)
• algorithms for finding several types of Eulerian trails
• Chinese Postman Problem (some necessary parts of matching theory will be introduced)
• Mazes

Additionally, we discuss some conjectures regarding characterizations of Eulerian graphs.

ECTS-Breakdown: 3 ECTS = 75 hours

25 h lecture
20 h homework preparation
29 h exam preparation
  1 h oral exam
----
75 h overall

Attention! There is no course on April 19, 2016!

The grade is based on active participation in the lecture, the discussion of optional homeworks and a final oral exam including all contents of the course.

Basic knowledge of graph theory is welcome but not mandatory.