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

Pascal Schweitzer