Till innehåll på sidan

Pascal Schweitzer: Aspects of the Graph Isomorphism Problem: Coloring Techniques, Hereditary Graph Classes and Parameterized Complexity

Pascal Schweitzer, European Post-Doctoral Institute

Tid: On 2012-03-28 kl 10.15 - 12.00

Plats: Room 3733, Department of Mathematics, KTH, Lindstedtsvägen 25, 7th floor

Exportera till kalender

The graph isomorphism problem asks whether there is an adjacency and non-adjacency preserving bijection between the vertices of two input graphs. The problem lies in the complexity class NP, but neither is the problem known to be NP-complete nor has a polynomial-time algorithm been developed. Its complexity status thus remains open.

I will talk about various combinatorial aspects of the graph isomorphism problem: To this end I will give an overview over the reoccurring techniques and known results. I will then talk about structural insights into some hereditary graph classes and their implications for the isomorphism problem. I will also mention some results regarding the parameterized complexity of the problem. These results were obtained jointly with Stefan Kratsch.

Tillhör: Stockholms Matematikcentrum
Senast ändrad: 2012-03-21