Monday, April 22, 2013
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
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