Inhalt

Wir werden uns grob mit den folgenden Themengebieten der algorithmischen Graphentheorie auseinandersetzen:

• kürzeste Wege,
• Minimale Spannbäume,
• Rundreiseprobleme (Euler- und Hamiltonkreise),
• Flüsse,
• Modellierung mittels (ganzzahliger) linearer Programmierung,
• Matchings,
• planare Graphen,
• Färbbarkeit,
• Approximation und Fest-Parameter-Berechenbarkeit.

Lernziele

Am Ende dieses Kurses sind HörerInnen in der Lage typische Probleme der Informatik als Graphenprobleme zu modellieren. Außerdem können TeilnehmerInnen entscheiden, welche Werkzeuge aus der Vorlesung dabei helfen ein gegebenes Graphenproblem algorithmisch zu lösen. Studierende lernen in diesem Kurs vertieft die Laufzeit von gegebenen Graphalgorithmen abzuschätzen.

Weiterführende Veranstaltungen

• Vorlesung Algorithmische Geometrie (jedes WS)
• Vorlesung Approximationsalgorithmen (jedes WS)
• Vorlesung Exakte Algorithmen (unregelmäßig)
• Vorlesung Visualisierung von Graphen (jedes SS)
• Seminar Visualisierung von Graphen (o.ä., jedes WS und dieses SS)

Siehe auch unsere Veranstaltungsübersicht