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 Advanced Algorithms (jedes WS)
• Vorlesung Visualisierung von Graphen (jedes SS)
• Vorlesung Algorithmen für geographische Informationssysteme (jedes SS)
  
• Vorlesung Exakte Algorithmen (jedes SS)
• Seminar Visualisierung von Graphen (o.ä., jedes WS)
• Seminar Algorithmen für Programmierwettbewerbe (derzeit jedes WS und SS)
  

Siehe auch unsere Veranstaltungsübersicht