Algorithmen in der Diskreten Mathematik

Diese Vorlesung deckt Graphenalgorithmen aus verschiedenen algorithmischen Bereichen ab; es werden zusätzlich graphentheoretische
Hintergründe gegeben, wenn sie für die Problemstellung relevant sind.

Vorlesung: Mittwoch 10:45-12:15 im Raum C112 (Curiebau)
Dozent: Jens M. Schmidt
Übung: Mittwoch 09:00-10:30 im Raum C112 (Curiebau), gerade Kalenderwochen
Tutor: Jens M. Schmidt
SWS: 2V+1Ü
Zielgruppe: Mathematik Master 2. Fachsemester
Voraussetzungen: Grundlagen in Diskreter Mathematik, Algorithmen und Komplexität
Prüfung: Am Ende des Semesters wird eine mündliche Prüfung angeboten.
Literatur:






Datum Inhalt Übung Material
02.04.2014 Basics Einführung, Typische Graphenprobleme in P und NP, unit-cost RAM 01.pdf
09.04.2014 Basics Graph-Datenstrukturen, Bipartite Graphen, Topologische Sortierung Ueb01.pdf
16.04.2014 Connectivity Dreiecksfreie Graphen, Starke Zusammenhangskomponenten, Lineare Laufzeiten, Knoten- und Kantenzusammenhang
03.pdf
23.04.2014 Connectivity Einer für alle: Chain Decompositions und die Berechnung von Ohrenzerlegungen, 2-Edge- und 2-Vertex-Connectivity, Block-Cut-Trees und mehr Ueb02.pdf 04.pdf
30.04.2014 Connectivity Starke Orientierungen, st-Numberings und -Orientations, k-Kontrahierbare Kanten, Definition Flüsse
07.05.2014 Flows Restnetzwerke, Max-Flow Min-Cut Theorem Ueb03.pdf
14.05.2014
Dies Academicus
21.05.2014 Flows Ford Fulkerson, Rationale vs Irrationale Kapazitäten, Fat Pipe-Algorithmus, Edmonds-Karp
28.05.2014 Flows Preflow-Push Algorithmus mit Laufzeit O(n^2 sqrt(m)) Ueb04.pdf 05.pdf
04.06.2014 Flows+Matchings Folgerungen: Satz von Hall, Satz von König, Disjunkte Pfade und Menger-Theoreme
11.06.2014 Planar Graphs Einbettungen, Dualgraph+Repräsentation, Dichte minorenabgeschlossener Graphen
18.06.2014 Planar Graphs Nachbarschaftsanfragen, Minimale Spannbäume in O(m+n log log n) und Linearzeit Ueb05.pdf
25.06.2014 Planar Graphs Planar Separator Theorem, Anwendungen des Planar Separator-Theorems
02.07.2014 Connectivity Algorithmen für Knoten- und Kantenzusammenhang, Maximal Adjacency Orderings
06.pdf
09.07.2014 Jens ist außer Haus