Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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



Letzte Aktualisierung: 10.04.2013