Algorithmische Graphentheorie

Diese Vorlesung behandelt ausgewählte Bereiche der Algorithmischen Graphentheorie mit einem Fokus auf Zusammenhangsprobleme.

Vorlesung: Dienstag 09:00-10:30 im Raum C112
Dozent: Jens M. Schmidt
Übung: Mittwoch 09:00-10:30 im Raum C112 (gerade Kalenderwochen)
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: Mathematik Master 2. Fachsemester
Voraussetzungen: Kombinatorische Optimierung (wünschenswert), Einführung in die Diskrete Mathematik, Graphen und Algorithmen
Prüfung:

Prüfungsvoraussetzungen sind die regelmäßige und aktive Mitarbeit in den Übungen und das Vorstellen eigener Lösungen von Übungsaufgaben. Am Ende des Semesters wird eine mündliche Prüfung angeboten.
Literatur:







Datum Inhalt Slides (Druckv.) Übung
11.10.2016 Basics Unit-cost RAM, Graph-Datenstrukturen, Bipartite Graphen, Topologische Sortierung ueb01.pdf
18.10.2016 Small Connectivity Starke Zusammenhangskomponenten, 2-Zusammenhang mit Chain Decompositions: Ohrendekompositionen, 2-Kanten- und 2-Zusammenhangstests, ... Slides
25.10.2016 Small Connectivity ...st-Orientierungen und -numberings, starke Orientierungen, Block-Cut-Trees und 2-kontrahierbare Kanten in linearer Zeit Slides ueb02.pdf
01.11.2016 Small Connectivity 3-Zusammenhang, Tutte Splits, 3-Zusammenhangskomponenten
Slides
08.11.2016 Small Connectivity SPQR-Bäume + Berechnungsidee, Anzahl kombinatorischer Einbettungen planarer Graphen Slides ueb03.pdf
15.11.2016 Certifying Algorithms Zertifizierende Algorithmen für 3-Zusammenhang, BG-Operationen, Bijektion zu BG-Pfaden und Existenz, Berechnung in Zeit O(n2) Slides
22.11.2016 Certifying Alg. +
Connectivity
Berechnung in Linearzeit, Tuttes Wheel-Theorem,
Flussbasierte Knoten- und Kantenzusammenhangstests, Even-Tarjan, Bestimmung der Zusammenhangszahlen
Slides ueb04.pdf
29.11.2016 Connectivity Maximal Adjacency Orderings, Forest Decompositions und Folgerungen, Intervall- und weitere Eigenschaften
06.12.2016 Connectivity Sparsification, Pendant Pairs, Kantenzusammenhang in Zeit O(nm), Linear Decay, Matulas (2+eps)-Approximation in Zeit O(n+m)
ueb05.pdf
13.12.2016 Connectivity Fluss-äquivalente Graphen, Gomory-Hu-Bäume für Graphen und symmetrische submodulare Mengenfunktionen Slides
20.12.2016 Connectivity Dynamische Graphen, Euler-Tour Bäume, Dynamischer Zusammenhang in polylogarithmischer Zeit ueb06.pdf
10.01.2107 Planar Graphs Planaritätstest von Boyer-Myrvold in Zeit O(n): Walkup, Walkdown, Korrektheit, Kuratowski-Minorenextraktion Slides
17.01.2107 Planar Graphs Geradlinige Zeichnungen, Kanonische Ordnungen, Shift-Algorithmus, Mondshein-Sequenz und Anwendungen: Alternativer Planaritätstest, Unabhängige Spannbäume, 3-Partitionsproblem Slides
Slides
ueb07.pdf
24.01.2107 Treewidth Partielle k-Bäume, Baumzerlegungen, Äquivalenz, Separatoren und Abgeschlossenheit, Berechnung der Baumweite
31.01.2107 Treewidth Dynamische Programmierung über Baumzerlegungen, 3-Färbbarkeit in Zeit O(32kkn), Schöne Baumzerlegungen, Courcelles Theorem und Konsequenzen
ueb08 (Bonus).pdf