Das Graph Isomorphie Problem
Vorlesung im Wintersemester 2014/2015
Inhalt
Das Graphisomorphieproblem ist eins der wichtigsten offenen Probleme der theoretischen Informatik. In den vergangenen 40 Jahren wurden eine ganze Reihe von Teilresultaten bewiesen. Diese Resultate basierten auf Grundlagen von verschiedenen Bereichen der theoretischen Informatik und diskreten Mathematik. Teil der Vorlesung werden die Highlights des Graphisomorphieproblems, beginnend mit den Resultaten von 1970 bis hin zu aktuellen Ergebnissen. Für Jedes dieser Resultate stellen wir die verwendeten Techniken und den verwendeten Kontext vor.
Voraussetzungen
Die Grundvorlesungen des Informatikstudiums werden benötigt.
Literaturhinweise
The Graph Isomorphism Problem: Its Structural Complexity [Köbler, Schöning, Toran]
Organisation
Vortragssprache in Deutsch oder Englisch.
Dozent