#
Monday Lecture and Colloquium

**Monday, April 22, 2013**

Technische Universität Berlin

Fakultät II, Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

### Martin Grohe -
RWTH Aachen

###
The Graph Isomorphism Problem

*Abstract:*

The question of whether there is a polynomial time algorithm
deciding whether two graphs are isomorphic has been a one of the best known
open problems in theoretical computer science for more than forty
years. Indeed, the graph isomorphism problem is one of the very few natural
problems in NP that is neither known to be in P nor known to be
NP-complete. The question is still wide open, but a number of deep partial
results giving polynomial time algorithms for specific classes of graphs are
known.

After an introductory survey on the graph isomorphism problem, in my
talk I will discuss connections between a basic combinatorial
isomorphism algorithm known as the Weisfeiler-Lehman algorithm and a
linear programming approach to graph isomorphism testing.

** Colloquium - 16:00**

### t.b.a.

###

*Abstract:*

Letzte Aktualisierung:
10.04.2013