ZBVI.01k
|
Algorithmische Graphentheorie |
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.
Literatur
|