Vorlesung Anwendungen von Graphzerlegungen in Algorithmik und Logik

Aktuelles

Das Kapitel 2 des Skipts wurde nun vervollständigt und kann weiter unten herunter geladen werden.

Einführung

Viele der in der Praxis auftretenden algorithmischen Probleme auf Graphen sind NP-schwer und lassen daher keine effizienten Verfahren zu ihrer Lösung erwarten. Klassische Beispiele dafür sind Probleme aus der Routenplanung oder Färbungsprobleme. Andererseits werden viele dieser Probleme einfach, wenn man sich nur auf Bäume oder planare Graphen beschränkt. Planare Graphen sind z.B. bei der Routenplanung interessant, da die meisten Straßen- oder S-Bahn-Netze nahezu planar sind. Ausgehend von diesen Ergebnissen versucht man, möglichst große Klassen von Graphen zu identifizieren, die Polynomialzeit-Lösungsverfahren für wichtige algorithmische Probleme erlauben. Im Rahmen dieser Vorlesung werden wir uns mit effizienten Lösungsverfahren für algorithmische Probleme auf eingeschränkten Klassen von Graphen befassen. Zunächst werden dabei Methoden zum Lösen solcher Probleme auf planaren Graphen behandelt. Anschließend werden wir auf Verallgemeinerungen von Bäumen und planaren Graphen eingehen, z.B. auf "baumartige" Graphen beschränkter Baumweite oder Graphenklassen mit verbotenen Minoren. Des Weiteren werden wir Constraint-Satisfaction-Probleme auf Hypergraphen beschränkter Hyperbaumweite effizient lösen. Grundkenntnisse in Graphentheorie und Vertrautheit mit Graphzerlegungen sind hilfreich aber nicht nötig. Alle für die Vorlesung benötigten Begriffe der Graphentheorie werden neu eingeführt.

Inhaltverzeichnis

1. Einführung
2. Baumzerlegungen
3. Planare Graphen
4. Lokale Baumweite
5. Minoren
6. Constraint-Satisfaction, Datenbankanfragen und Homomorphismen
7. Cover-Baumweite (Hyperbaumweite)

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, 11 - 13 und Donnerstags, 13 - 15 Uhr im Erwin-Schrödinger Zentrum, Raum 0'313

Vorlesungsbeginn ist Dienstag, der 17.4.2007.

 

Dozenten

Prof. Dr. Stephan Kreutzer	(erste Hälfte der Vorlesung)
Dr. Isolde Adler	(zweite Hälfte der Vorlesung)

Übungen

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

Zeit und Raum

Dienstag, 13 - 15 Uhr im Erwin-Schrödinger Zentrum, Raum 1'306

 

Übungsgruppenleiter

Sebastian Ordyniak

Marc Thurley

Übungsaufgaben

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

• Übungsblatt 1
• Übungsblatt 2
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6
• Übungsblatt 7
• Übungsblatt 8
• Übungsblatt 9
• Übungsblatt 10
• Übungsblatt 11
• Übungsblatt 12

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 Übungaufgaben erworben werden.

Materialien

Die Folien zur ersten Vorlesung können Sie hier finden.

Erste Vorläufige Version des Skripts:

• Titelblatt und Inhaltsverzeichnis
• Kapitel 2 (vervollständigt)
• Kapitel 3
• Kapitel 4
• Kapitel 5
• Kapitel 6
• Kapitel 7
• Anhang A Im Anhang A des Skipts werden grundlegende Notationen festgelegt.
• Index und Literaturangaben

Literatur

Die Vorlesung orientiert sich nicht an einem konkreten Buch. Literaturangaben zu den einzelnen Teilen der Vorlesung werden jeweils in der Vorlesung bekannt gegeben. Im folgenden stellen wir einige Bücher vor, die als Zusatzlektüre geeignet sind.

Graphentheorie allgemein:

R. Diestel, Graphentheorie, 3. Auflage, Springer-Verlag, 2006
Sehr schönes Buch zur Graphentheorie. Unsere Notation richtet sich weitgehend nach diesem Buch. Es enthält ein ausführliches Kapitel zu Baumzerlegungen und Minoren. Allerdings ist das Buch völlig frei von Algorithmen.
Eine Online-Version des Buches kann hier betrachtet werden.

Algorithmen:

Zu Algorithmen auf Graphzerlegungen ist (unseres Wissens) noch kein Standard-Werk erschienen. Es gibt aber verschiedene Vorlesungsskripte von diversen Universitäten. Am nächsten kommen dem Thema der Vorlesung vielleicht noch folgende Bücher, die verschiedene Algorithmen auf Baumzerlegungen, planaren Graphen usw. enthalten. Wir empfehlen besonders das neuer Buch von Flum und Grohe zur Hintergrundlektüre.

• J. Flum und M. Grohe, Parameterized Complexity Theory, Springer-Verlag, 2006.
  
• R. G. Downey und M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1998

Anwendungen der Graphentheorie:

Anwendungen graphentheoretischer Verfahren in anderen Wissenschaftsdisziplinen können z.B. in folgenden Büchern gefunden werden.

• R. J. Wilson und J. J. Watkins, Graphs. An Introductionary Approach, Wiley Verlag.
  (Enthält sehr viele Beispiele von Anwendungen in verschiedenen Bereichen.)
• L.R. Foulds, Graph Theory Applications, Springer-Verlag