## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, February 28, 2013, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Pascal Schweitzer

## Aspects of the Graph Isomorphism Problem

The graph isomorphism problem asks whether there is an adjacency and non-adjacency preserving bijection between the vertices of two input graphs. The problem lies in the complexity class NP, but neither is the problem known to be NP-complete nor has a polynomial-time algorithm been developed. Its complexity status thus remains open. I will talk about some algorithmic aspects of the graph isomorphism problem: To this end I will give an overview over the reoccurring techniques and classical results. I will then describe more recent results and talk about graph isomorphism in the context of random graph classes.

Information for students and suggested topics for student talks