Prüfungsstoff für die Vorlesung
"Effiziente Algorithmen I"

Grundlegende Graphenalgorithmen

• Repräsentation von Graphen
• Breadth-First Search und Depth-First Search, Eigenschaften
• Topologisches Sortieren
• Starke Zusammenhangskomponenten

• Bäume und Wälder, Algorithmen von Kruskal und Prim, Implementierung
• Maximale Branchings, Algorithmus von Edmonds
• TSP-Relaxierungen

• Eigenschaften kürzester Wege
• Dijkstra- und Bellman-Ford-Algorithmus
• Kürzeste Wege in azyklischen Digraphen, Knapsack-Problem
• Kürzeste Wege zwischen allen Knotenpaaren
• Floyd-Warshall- und Johnson-Algorithmus
• Varianten kürzester Wege, Bottleneck-Probleme
• Kreise mit bestem Kosten-Zeit-Verhältnis

• Ungarische Methode, Satz von Egervary-König
• Algorithmus von Achatz, Kleinschmidt und Paparizzos

• Algorithmus von Ford-Fulkerson, Max-Flow-Min-Cut-Theorem
• Edmonds-Karp-Variante, Skalierungsalgorithmus
• Preflow-Push-Algorithmus
• Behandlung von unteren Schranken und Knotenkapazitäten

• Algorithmus von Nagamochi und Ibaraki
• Algorithmus von Karger
• Minimale Schnitte zwischen allen Knotenpaaren, Gomory-Hu-Baum

• Optimalitätsbedingungen
• Negative-Kreise-Verfahren
• Kürzeste-Wege-Verfahren
• Primale Netzwerk-Simplexalgorithmus, Basistausch

• Maximale Matchings in bipartiten Graphen
• Maximale Matchings in allgemeinen Graphen, Algorithmus von Edmonds
• Chinesisches Postbotenproblem