Algorithmic Graph Theory (Algorithmische Graphentheorie)

• 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, HS 102, Building 10.50
  • Wednesday, 09:45 AM – 11:15 AM, Room 301, HS 102, Building 10.50
• Credits: 5 ECTS
• Exam: Oral exams at the end of the term
• Language: English

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.

Exercise sheets will be published here regularly.