Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 28, 2013, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Pascal Schweitzer
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.
Automatic MiSe System Software Version 1.4803M | admin login