Vorlesung: Effiziente Graphenalgorithmen

Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluß daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten. Die Veranstaltung vermittelt folgende Kompetenzen: - Grundlegende Algorithmen und Datenstrukturen auf Graphen beherrschen - Korrektheit und Laufzeit von Graphenalgorithmen analysieren - Exakte und heuristische Möglichkeiten zur Effizienzsteigerung anwenden - Ausnutzen spezieller Eigenschaften (Planarität, Dünnbesetztheit) und effizienter Datenstrukturen - Urteilsfähigkeit, welche Verfahren in der Praxis effizient einsetzbar sind - Implementierung verschiedener Varianten - Modellierung verschiedener Problemstellungen auf Basis von Graphen, u.a. Problemen aus dem Knowledge Processing und der Sprachtechnologie