Algorithmic Graph Theory

Prof. Dr. Daniel Neuen

The goal of this course is to study advanced methods for analysis and algorithm design on graphs. Graphs are ubiquitous in computer science for modeling, e.g., all kinds of physical and virtual networks, molecules, interactions between objects, etc. Many real-world problems can be formulated as theoretical problems on graphs, such as finding finding maximum matchings, graph colorings, vertex covers, and minimum cuts.

In this course, we study various basic and advanced topics in graph theory that can be used for analysis and algorithm design on graphs. In particular, we study graph cuts, coloring problems, subgraph and minor relations in graphs, random graphs, planar graphs, and the design of fast algorithms for problems related to these notions.

Prerequisites: Successful completion of basic course on "Algorithmen und Datenstrukturen".

Dates:

• Tue., 13:00-14:30, APB/E005/U (Lecture)
• Wed, 14:50-16:20, APB/E005/U (Exercise)
• Fri, 13:00-14:30, APB/E005/U (Lecture)