Logbuch Effiziente Algorithmen - Sommer 2026
Vorlesung 6 -- 29.04.2026:
Material:
Maximum Matching in allgemeinen Graphen, augmentierende Pfade, ungerade Kreise, Blüten, Edmonds Algorithmus, Beispiele- Notizen, Abschnitt 2.2.
Vorlesung 5 -- 27.04.2026:
Material:
Varianten von Matching in bipartiten Graphen: Charakterisierung perfekter Matchings, maximum und perfekte Matchings mit minimalen Kosten, Anwendung von Flüssen mit minimalen Kosten, Successive-Shortest-Path Algorithmus mit Nutzung von Knotenpotenzialen und Dijkstra's Algorithmus berechnet ein perfektes Matching mit minimalen Kosten in bipartiten Graphen in Laufzeit O(n3).- Notizen, Abschnitt 2.1 (ab Theorem 5).
Vorlesung 4 -- 22.04.2026:
Material:
Flüsse mit minimalen Kosten, Optimalitätskriterien: (1) Keine Kreise mit negativen Kosten im Restnetzwerk, Cycle-Canceling Algorithmus; (2) Iterative Erhöhung mittels billigster augmentierender Wege, Successive-Shortest-Path Algorithmus. Implemetation mit Dijkstra's Algorithmus, Knotenpotenziale, angepasste Kostenfunktion, Update der Potenziale bei billigsten augmentierenden Wegen.- Notizen, Abschnitt 1.2.
Vorlesung 3 -- 20.04.2026:
Material:
Preflows, Höhenfunktionen, Kompatibilität, PreflowPush Algorithmus, Beispiel. Analyse der Laufzeit über die Anzahl der Relabel Operationen (maximal 2n(n-2)) und der saturierenden Push-Operationen (maximal 2nm). Potenzialfunktion zur Analyse der nicht-saturierenden Push-Operationen (maximal 4n2m).- Notizen, Abschnitt 1.1.2.
Vorlesung 2 -- 15.04.2026:
Material:
Max-Flow-Min-Cut Theorem mit Beweis, Anwendung auf die Berechnung bipartiter Matchings mit größter Kardinalität, Skalierungsvariante mit (schwach) polynomieller Laufzeit von O(m2 log C), Edmonds-Karp-Variante mit stark polynomieller Laufzeit von O(nm2).- Notizen, Abschnitt 1.1.1 (ab Theorem 1) und Abschnitt 2.1.1 (nur Theorem 5).
Vorlesung 1 -- 13.04.2026:
Material:
Organisatorisches, Details zum Übungsbetrieb. Flussprobleme, Definition Flussnetzwerk, Fluss, Wert des Flusses, Restnetzwerk und augmentierende Pfade. Ford-Fulkerson-Algorithmus, Korrektheit, Laufzeit. s-t-Schnitte, Kapazität des Schnittes, Fluss über einen Schnitt, Max-Flow-Min-Cut Theorem.