The Graph Isomorphism Problem
Lecture in Winter Term 2014/2015
The Graph Isomorphism Problem is one of the most important open problems of the theoretical computer sciences. Over the course of the last 40 years there had been results in partially solving the problem, based on principles from various fileds of the theoretical computer science and discrete mathematics. Part of the course will be to present the highlights of graph isomorphism problem solving, beginning with the early results from 1970s to recent events. Every one of the results will be acompanied by an introduction of the used technique and the used context.
The basic lectures of B.Sc. in computer science are required.
The Graph Isomorphism Problem: Its Structural Complexity [Köbler, Schöning, Toran]
Lecture will be held in German and English.