Lehrstuhl für
Diskrete Mathematik und Grundlagen der Informatik

Algorithmische Graphentheorie

Mittwochs	11.30 Uhr - 13.00 Uhr	ZHG/SR1
Donnerstags	13.45 Uhr - 15.15 Uhr	ZHG/SR4 (am 18.11., 02.12. und 09.12. im HG 0.19)

Eine Vielzahl interessanter Optimierungsprobleme auf Graphen ist algorithmisch sehr schwer zu lösen. Als Beispiel sei das Graphfärbungsproblem oder das Hamiltonkreisproblem genannt. Betrachtet man praktische Anwendungen in denen solche Optimierungsprobleme eine Rolle spielen, so sind für die entsprechenden Graphen oft sehr spezielle Struktureigenschaften bekannt. Setzt man diese Eigenschaften voraus, lassen sich die betrachteten Optimierungsprobleme oft mit sehr schnellen Algorithmen exakt lösen.

Das Gebiet der Algorithmischen und Strukturellen Graphentheorie beschäftigt sich mit der Untersuchung solcher Struktureigenschaften und dem Entwurf effizienter Algorithmen für spezielle Graphenklassen. In dieser Vorlesung werden wir uns mit einer Reihe von Graphenklassen genauer beschäftigen, so z.B. mit Intervallgraphen, chordalen Graphen, planaren Graphen und Vergleichbarkeitsgraphen. Für jede der Graphenklassen werden wir charakteristische Struktureigenschaften bestimmen, Erkennungsalgorithmen entwickeln und schließlich verschiedene effiziente Algorithmen für Optimierungsprobleme entwerfen.

Die Vorlesung wird als integrierte Veranstaltung angeboten, d.h. es werden regelmäßig Übungsblätter ausgegeben, die dann von den Teilnehmern bearbeitet und in integrierten Übungen besprochen werden. Die regelmäßige Teilnahme und Mitarbeit bei den Übungen ist Voraussetzung für die Teilnahmebestätigung.

Übungsblätter

Literatur

• M.C. Golumbic: "Algorithmic Graph Theory and Perfect Graphs", Elsevier, 2004. Link zum Buch
• A. Brandstädt, V.B. Le, J.P. Spinrad: "Graph Classes: A Survey", SIAM, 1999.
• D.B. West: "Introduction to Graph Theory - 2nd ed.", Prentice Hall, 2001.
• J.P.Spinrad: "Efficient Graph Representations", ACM, 2003.