Algorithmic Graph Theory (Algorithmische Graphentheorie)
Summer Term 2025
- Lecture: Torsten Ueckerdt
- Exercise Class: Laura Merker, Samuel Schneider
- Schedule: on average one lecture every week and one exercise class every two weeks
- Monday, 11:30 AM – 1:00 PM, Room 301, CS Building 50.34
- Wednesday, 09:45 AM – 11:15 AM, Room 301, CS Building 50.34
- Credits: 5 ECTS
- Exam: Oral exams at the end of the term
- Language: English
Topic
Many basic problems that arise in many contexts, such as coloring problems or finding maximum independent sets and maximum cliques, are NP-hard in general graphs. However, instances of these difficult problems that occur in applications are often much more structured and can therefore be solved efficiently. The lecture first introduces perfect graphs and their most important subclass, chordal graphs. Then, it presents algorithms for various generally NP-hard problems on chordal graphs. Subsequently, in-depth concepts such as comparability graphs are discussed, with the help of which various other graph classes (interval, split and permutation graphs) can be characterized and recognized. Finally, tools for the design of specialized algorithms for these graph classes are presented.
Schedule (subject to change)
| Monday | Wednesday | ||
|---|---|---|---|
| 21.04 | - | 23.04 | Lecture 1 |
| 28.04 | Lecture 2 | 30.04 | Exercise Class 1 |
| 05.05 | Lecture 3 | 07.05 | Exercise Class 2 |
| 12.05 | Lecture 4 | 14.05 | Lecture 5 |
| 19.05 | Lecture 6 | 21.05 | Exercise Class 3 |
| 26.05 | Lecture 7 | 28.05 | Lecture 8 |
| 02.06 | Lecture 9 | 04.06 | Exercise Class 4 |
| 09.06 | - | 11.06 | - |
| 16.06 | - | 18.06 | - |
| 23.06 | Lecture 10 | 25.06 | Lecture 11 |
| 30.06 | Lecture 12 | 02.07 | Exercise Class 5 |
| 07.07 | Lecture 13 | 09.07 | - |
| 14.07 | Lecture 14 | 16.07 | Exercise Class 6 |
| 21.07 | Lecture 15 | 23.07 | Lecture 16 |
| 28.07 | - | 30.07 | Exercise Class 7 |
Exercise Sheets
Exercise sheets will be published here regularly.