|
Lehrende: Dr. rer. nat. Kord Eickmeyer
Veranstaltungsart:
Vorlesung und Übung
Orga-Einheit: FB04 Mathematik
Anzeige im Stundenplan:
Graph Struct. Theory
Fach:
Anrechenbar für:
Semesterwochenstunden:
3
Unterrichtssprache:
Englisch
Min. | Max. Teilnehmerzahl:
- | -
Lehrinhalte:
erststufige Logik: Lokalität und Gaifman-Normalform,
monadische zweitstufige Logik: Ausdrucksstärke auf Bäumen; Baumautomaten
Satz v. Feferman und Vaught
Graphentheorie: Planarität und Einbettbarkeit in höhere Flächen, Minoren und topologische Minoren, Separatoren, Baumzerlegungen, Baum- und Pfadweite, Graphstrukturtheorem von Robertson und Seymour
Meta-Theoreme: Satz v. Courcelle, Effiziente Auswertbarkeit von FO auf minorenabgeschlossenen Graphklassen
weitere Themen evtl.: flache Minoren, beschränkte Expansion, nirgendwo dichte Graphen, untere Schranken
Literatur:
\begin{itemize}
\item Flum, Grohe: \emph{Parameterized Complexity}, Springer Verlag
\item Diestel: \emph{Graph Theory}, Springer Verlag
\item Ebbinghaus, Flum: \emph{Finite Model Theory}, Springer Verlag
\item B. Courcelle: Graph rewriting: an algebraic and logic approach, in: \emph{Handbook of theoretical computer science (vol. B): formal models and semantics}, MIT Press, Cambridge, MA, USA (1990), pp. 193–242
\item M. Grohe: Logic, graphs, and algorithms, in: J. Flum, E. Grädel, T. Wilke (Eds.), \emph{Logic and Automata: History and Perspectives}, Amsterdam University Press, Amsterdam (2007), pp. 357–422
\item M. Grohe and S. Kreutzer: Methods for algorithmic meta theorems, in: \emph{Model Theoretic Methods in Finite Combinatorics} 558 (2011): 181-206.
\end{itemize}
Voraussetzungen:
\glqq mathematical maturity\grqq. Previous exposition to logics and/or graph theory is desirable but not strictly necessary. Some background knowledge in computational complexity and algorithms would be a bonus.
Zusätzliche Informationen:
Vertiefungsniveau
|
