Algorithmische Graphentheorie (Sommer 2018)

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

Vorlesung: Donnerstag 11:00-12:30 im Raum C110
Dozent: Jens M. Schmidt
Übung: Montag 15:00-16:30 im Raum C112 (gerade Kalenderwochen)
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: Mathematik Master 2. Fachsemester
Voraussetzungen: Kombinatorische Optimierung (wünschenswert), Graphentheorie, Graphen und Algorithmen, Einf.  in die Diskrete Mathematik
Prüfung:

Zum Ende der Vorlesungszeit wird eine mündliche Prüfung angeboten. Prüfungsvoraussetzung ist, mindestens 50% der Gesamtanzahl aller Übungsaufgaben zu lösen, diese zu Beginn jeder Übung dem Übungsleiter anzuzeigen, und falls vom Übungsleiter gewünscht, deren Lösungen fehlerfrei und sicher vorzutragen. Lösungen zu den Programmieraufgaben müssen dem Übungsgruppenleiter vor der Übung per Email mit Source-Code, ausführbarer Datei und (falls vorhanden) Ausgabe zugesendet werden.
Literatur:







Nr.
Inhalt Slides (Druckv.) Übung
01. Small Connectivity Einführung, unit-cost RAM, Graph-Datenstrukturen, Topologische Sortierung
ueb01.pdf
02. Small Connectivity 2-Zusammenhang mit Chain Decompositions:
Ohrendekompositionen, 2-Kanten- und 2-Zusammenhangstests, st-Orientierungen und -numberings (Badent 2002, Easy st-Numberings 2019)starke Orientierungen, Block-Cut-Trees und 2-kontrahierbare Kanten in jeweils Zeit O(m)
Slides
03. Small Connectivity 3-Zusammenhang, Tutte Splits, 3-Zusammenhangskomponenten
Slides ueb02.pdf
04. Small Connectivity SPQR-Bäume + Berechnungsidee, Anzahl kombinatorischer Einbettungen planarer Graphen Slides
05. Certifying Algorithms Zertifizierende Algorithmen für 3-Zusammenhang, BG-Operationen, Bijektion zu BG-Pfaden und Existenz, Berechnung in Zeit O(n2) Slides ueb03.pdf
06.
Christi Himmelfahrt

07. Certifying Alg. +
Connectivity
Berechnung in Linearzeit, Tuttes Wheel-Theorem,
Flussbasierte Knoten- und Kantenzusammenhangstests, Even-Tarjan, Bestimmung der Zusammenhangszahlen
Slides ueb04.pdf
08. Connectivity Maximal Adjacency Orderings, Forest Decompositions und Folgerungen, Intervall- und weitere Eigenschaften

09. Connectivity Sparsification, Pendant Pairs, Kantenzusammenhang in Zeit O(nm), Linear Decay, Matulas (2+eps)-Approximation in Zeit O(n+m)

ueb05.pdf
10. Connectivity Fluss-äquivalente Graphen, Gomory-Hu-Bäume für Graphen und symmetrische submodulare Mengenfunktionen Slides
11. Connectivity Dynamische Graphen, Euler-Tour Bäume, Dynamischer Zusammenhang in polylogarithmischer Zeit
ueb06.pdf
12. Planar Graphs Planaritätstest von Boyer-Myrvold in Zeit O(n): Walkup, Walkdown, Korrektheit, Kuratowski-Minorenextraktion Slides
13. Planar Graphs Geradlinige Zeichnungen, Kanonische Ordnungen, Shift-Algorithmus, Mondshein-Sequenz und Anwendungen: Alternativer Planaritätstest, Unabhängige Spannbäume, 3-Partitionsproblem, Planare st-Orientierungen, Barnettes Theorem Slides
Slides
ueb07.pdf
14. Treewidth Partielle k-Bäume, Baumzerlegungen, Äquivalenz, Separatoren und Abgeschlossenheit, Berechnung der Baumweite

15. Treewidth Dynamische Programmierung über Baumzerlegungen, 3-Färbbarkeit in Zeit O(32kkn), Schöne Baumzerlegungen, Courcelles Theorem und Konsequenzen
ueb08 (Bonus).pdf