Abstract:The question of whether there is a polynomial time algorithm deciding if 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. Very recently, Babai gave a quasi polynomial time isomorphism algorithm. Despite of this breakthrough result, the question for a polynomial algorithm remains wide open.
My talk will be a survey of recent progress on the isomorphism problem. I will focus on generic algorithmic strategies (as opposed to algorithms tailored towards specific graph classes) that have proved to be useful and interesting in various context, both theoretical and practical.
The Graph Isomorphism Problem
08.11.2016 17:15
Organiser:
VCLA
Location:
SR Zemanek, Favoritenstr. 9-11, EG