Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Vorlesung Baumzerlegungen von Graphen und ihre algorithmischen Anwendungen

Aktuelles  Einführung  Inhalt  Logbuch  Vorlesung  Übungen  Aufgaben  Prüfung Literatur

Aktuelles

Daniel Schenkel und Torsten Bosse haben netterweise ihre Vorlesungsmitschrift ins Netz gestellt.

Einführung

Zahlreiche wichtige algorithmische Probleme sind zwar komplexitätstheoretisch schwer, etwa NP-schwer, müssen aber in der Praxis dennoch gelöst werden. Dass dies gelingen kann, liegt daran, dass die in der Praxis vorkommenden Instanzen oft eine recht "einfache Struktur" aufweisen. Versucht man zu verstehen, was "einfache Struktur" hier bedeutet, so stößt man häufig auf Begriffe wie "baumartige" oder "hierarchisch strukturierte" Instanzen. Baumzerlegungen von Graphen geben eine natürliche Präzisierung solcher intuitiver Begriffe. Sie spielen eine wichtige Rolle sowohl in der Graphentheorie als auch in der Algorithmik. Insbesondere lassen sich sehr viele NP-schwere algorithmischen Probleme effizient auf Instanzen mit guten Baumzerlegungen lösen.

Diese Vorlesung ist eine Einführung in die Theorie der Baumzerlegungen und verwandter Zerlegungen und in ihre algorithmischen Anwendungen. Dabei sollen sowohl die graphentheoretischen Grundlagen als auch die algorithmischen Techniken vermittelt werden.

Inhalt

  1. Einführung
  2. Baumzerlegungen und Baumweite
  3. Algorithmen für und auf Baumzerlegungen
  4. Minoren
  5. Astweite

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungsbetrieb

Zeiten und Raum
Dienstags und Donnerstags 9-11 Uhr im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308
 
Dozent
Prof. Dr. Martin Grohe
Sprechstunde: Freitags 10:00 - 11:00

Übungen

Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.

Zeit und Raum
Donnerstags 11-13 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308
 
Übungsleiter
Dipl. Math. Mark Weyer
Sprechstunde: Mittwochs 14:00 - 15:00

Übungsaufgaben

Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.

Prüfung

Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungsaufgaben erworben werden.

Literatur

Zum Thema der Vorlesung gibt es derzeit noch keine Lehrbücher oder Monographien. Verweise auf die Fachliteratur werden im Laufe der Vorlesung gegeben.

Das letzte Kapitel des Buchs Graph Theory von Reinhard Diestel, (3. Auflage, Springer Verlag 2005) gibt eine Einführung in die graphentheoretischen Grundbegriffe, deckt aber nur eine kleinen Teil der Vorlesung ab und spart insbesondere algorithmische Aspekte aus.

Das Skript zu einer Vorlesung Einbettungen und Minoren von Graphen, die ich im Wintersemester 1999/2000 an der Universität Freiburg gehalten habe, enthält ebenfalls Teile dieser Vorlesung. Achtung: Ich habe das Skript nicht mehr überarbeitet oder korrigiert, es enthält sicherlich einige Fehler.

Software

Hier finden Sie eine Implementierung der in der Vorlesung vorgestelleten Algorithmen zum Berechnen von Baumzerlegungen in Python.

Last modified: Thu Oct 19 07:48:53 CEST 2006
Martin Grohe