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
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
Abstract: