Inhaltsverzeichnis

Graphen- und Netzwerkalgorithmen (ADM I)

Sommersemester 2007
Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 ,

1. Vorlesung, Di. 17.04.2007 

  Einleitung 
     Was ist und worum geht es in ADM?
  Propädeutik
     Fallbeispiel 1: 
        Stabile Hochzeiten
        Das Problem
        Formalisierung
        Der Gale-Shapley Algorithmus
        Stabilität der Lösung
        Optimalität für die Aktiven
2. Vorlesung, Do. 19.04.2007 
     Fallbeispiel 2: 
        'Interval Scheduling'
        Greedy Lösung
     Fallbeispiel 3: 
        Gewichtetes 'Interval Scheduling'
        Lösung durch Dynamisches Programmieren
     Fallbeispiel 4:
        Bipartites Matching 
        Die Hall Bedingung
        Lösung durch Greedy mit Nachbessern
     Fallbeispiel 5:
        Unabhängige Menge
        Umfassend, enthält (2) und (4)
        ist NP schwer
3. Vorlesung, Di. 24.04.2007 
  Graphen
       Grade und Handschlaglemma
       Zusammenhang und Bäume
       Schnitte
     Gerichtete Graphen
4. Vorlesung, Do. 26.04.2007 
       Schnitte in gerichteten Graphen
       Stark zusammenhängende Graphen 
       Topologische Sortierung
     Zykel- und Kozykelraum
5. Vorlesung, Do. 3.05.2007 
     Graphen durchmustern
       Generisch GraphSearch
       Depth First Search
       Breadth First Search
         Kürzeste Wege
6. Vorlesung, Di. 8.05.2007 
       Erkennung bipartiter Graphen
       Berechnung starker Zusammenhangskomponenten
     Euler Kreise
       Ein Algorithmus für Euler-Kreise
7. Vorlesung, Do. 10.05.2007 
     MST (Minimal aufspannende Bäume)
       Färbungsregeln und Färbungsinvariante
       Konkrete Algorithmen
         Boruvka / Kruskal / Prim
8. Vorlesung, Di. 15.05.2007 
     Optimale Arboreszenzen
       Eine Boruvka-artige Phase
       Struktur der Kreise
       Modifikation von Gewichten
       Kontraktion der Kreise
       Reexpansion
9. Vorlesung, Di. 22.05.2007 
     Kürzeste Wege
       Konservative Gewichte
       Lösung mit dynamischem Programmieren
         Bellmann-Ford
       Identifikation negativer Zykel
       Aktive Knoten statt Organisation in Runden
       Kürzeste Wege in azyklischen Graphen
10. Vorlesung, Do. 24.05.2007 
       Dijkstra-Algorithmus
     All-Pairs-Shortest-Path
       Optimaltätskriterium
       Floyd-Warshal
       Matrizenmultiplikation und Shortest-Path
11. Vorlesung, Di. 29.05.2007 
     Max Flow die Grundlagen
     [Vertr. Felix K.; EKreide auf der VLSeite]
12. Vorlesung, Do. 31.05.2007 
     Max Flow - Min Cut Thm. & Ford-Fulkerson Alg.
     [Vertr. Felix K.; EKreide auf der VLSeite]
13. Vorlesung, Di. 05.06.2007 
     Max Flow: Polynomielle Algorithmen
       Der Edmond-Karp Algorithmus
       Der Dinic Algorithmus
         Blockierende Flüsse
14. Vorlesung, Do. 07.06.2007 
     Preflow Algorithmen
       Push und Lift
       Korrektheit
15. Vorlesung, Di. 12.06.2007 
      Laufzeit des generischen Preflow Algorithmus
        Höhenschranke
        saturierende und nicht-saturierende Push
        Potentialfunktionen
      Die High-Push-Regel
        Max Fow in O(n^2\sqrt(m))
16. Vorlesung, Do. 14.06.2007 
     Min Cut
       Kontraktionslemma
       Min Cut ohne Max Flow
         MA-Ordnungen der Knoten
17. Vorlesung, Di. 19.06.2007 
      Schnitt Bäume (Gomory Hu)
        Die Konstruktion
          Submodularität und Kreuzungslemma
18. Vorlesung, Do. 21.06.2007 
     Kostenminimale Flüsse (Min Cost Flow)
       Shortest path als Spezialfall von MCF
       Optimalitätskriterium: Negative Zykel
       Der Cycle Canceling Algorithmus
19. Vorlesung, Di. 26.06.2007 
       Potentiale und reduzierte Kosten
       Optimalitätskriterium: Reduzierte Kosten
       Optimalitätskriterium: Komplementärere Schlupf
       Schwache Dualität
       Starke Dualität
20. Vorlesung, Do. 28.06.2007 
       Pseudoflüsse
       Der Successive Shortest Path Algorithmus
       Anwendung: Knickminimierung in orthogonalen Zeichnungen
21. Vorlesung, Di. 03.07.2007 
                  Knickminimierung und Min Cost Flow
     Matchings
       Bipartites Matching und Max Flow
       Satz von König-Egervary
       Alternierende und augmentierende Pfade
22. Vorlesung, Do. 05.07.2007 
       Alternierende und augmentierende Pfade
       Vertex Cover und ungerade Komponenten
       Die Tutte-Berge Formel
23. Vorlesung, Di. 10.07.2007 
       Eine 1/2 Approximation für maximal gewichtetes Matching
       Matchings und Determinantenevaluationen
       Matchings und Polytope
         Das Matching-Polytop P
         Das Polytop Q der Matchingungleichungen
         P ist in Q enthalten
24. Vorlesung, Do. 12.07.2007 
         Fuer bipartite Graphen gilt P=Q
     Komplexitätstheorie, P und NP
       Kodierungslänge
       Rechnermodelle
       Schwierige Probleme
       Die Klasse P
       Entscheidungsprobleme
25. Vorlesung, Di. 17.07.2007 
       Die Klasse NP
       P-Reduktionen
       NP-Vollständigkeit
       Satz von Cook (SAT ist NP-Vollständig)
       Reduktion von INDEP SET auf SAT
26. Vorlesung, Do. 19.07.2007 
   Kettenzerlegungen partieller Ordnungen
     (Varianten und Algorithmen)
        [Beamerpräsentation]

Zurück zur Vorlesungsseite.