Logbuch zur Vorlesung Baumzerlegungen von Graphen und ihre algorithmischen Anwendungen

Di, 18.4.06: Einf~rung, Algorithmen f~ die Einschr~kungen NP-schwerer Probleme auf B~me
Do, 20.4.06: Simpliziale Zerlegungen und chordale Graphen
Di, 25.4.06: Seriell-parallele Graphen und Netzwerke, au~rplanare Graphen, Planar Separator Theorem von Lipton und Tarjan, als Anwendung Approximationsalgorithmus f~ Independent Set auf planaren Graphen
Do, 27.4.06: Baumzerlegungen, Beispiele, einfache Eigenschaften
Di, 2.5.06: Helly Eigenschaft der B~me, Baumweite, kleine Baumzerlegungen, Kantenzahl <= Knotenzahl x Baumweite, Brombeeren und Brombeerdicke, Beispiele
Do, 4.5.06: Dualit~ssatz: Baumweite + 1 = Brombeerdicke
Di, 9.5.06: R~ber und Gendarmen Spiel, Baumweite + 1 = Gendarmenzahl, monotone und ged~htnislose Gewinnstrategien, simpliziale Baumzerlegungen, chordale Graphen und Baumzerlegungen, Baumweite +1 = Gr~e der Summanden eines chordalen Obergraphen
Do, 11.5.06: Charakterisierung von Baumweite durch Separatoren, Separationen
Di, 16.5.06: Berechnung von Trennern von zwei Mengen mit Hilfe von alternierenden Pfaden, als Korollar auch Satz von Menger
Do, 18.5.06: Berechnung von Baumzerlegungen ~er Separationen, Satz von Bodlaender (ohne Beweis), direkte Gewinnstrategien im RG-Spiel
Di, 25.5.06: Berechnung von Baumzerlegungen aus Gewinnstrategien, Algorithmen f~ F~barkeit und Hamiltonkreise auf Graphen kleiner Baumweite
Do, 1.6.06: Algorithmus f~ SAT f~ Formeln mit Inzidenzgraphen kleiner Baumweite, Minoren, kurze ~ersicht ~er Minorentheorie und Robertson und Seymours Minorensatz
Di, 6.6.06: Charakterisierung von Graphen der baumweite <=2 durch verbotenen Cliquenminoren, der Gittersatz, Anfang des Beweises
Do, 8.6.06: Beweis des Gittersatzes: Baumweite -> Gewebe
Di, 13.6.06: Beweis des Gittersatzes: Gewebe -> Gewirre
Do, 15.6.06: Beweis des Gittersatzes zu Ende
Di, 20.6.06: Submodulare und symmetrische Mengenfunktionen, Beispiele, Astzerlegungen und Astweite
Do, 22.6.06: Ausrichtungen, Ausrichtung -> Astweite
Di, 29.6.06: Pseudozerlegungen und exakte Pseudozerlegungen
Do, 1.7.06: Dualitätssatz
Di, 4.7.06: Astweite von Graphen, Trauben
Do, 6.7.06: Astweite = Traubendicke, Baumweite und Astweite
Di, 11.7.06: Verbundene Mengen, Charakterisierung der Astweite durch verbundene Mengen (weiter)
Do, 13.7.06: Charakterisierung der Astweite durch verbundene Mengen (fertig), polynomielle Repräsentationen von Mengenfunktionen, Minimierung submodularer Funktionen
Di, 18.7.06: Polynomieller Approximationsalgorithmus für Astweite

Last modified: Thu Jul 20 14:30:08 CEST 2006
Martin Grohe