MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The Graph Isomorphism problem: techniques from structural graph theory and canonical decompositions

Pascal Schweitzer
RWTH Aachen University
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 16 February 2016
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

As a recent breakthrough result of Babai ignites excitement about the graph isomorphism problem, the quest to resolve its complexity continues.
After a brief overview over the current landscape of results, I describe some decomposition techniques arising in particular in the structural theory of graphs
with a forbidden minor. General structure theorems yield canonical decompositions whose parts correspond to the maximal tangles.
These tangles may be viewed as describing "k-connected components". I will describe algorithmic versions of such theorems.

These algorithmic versions at hand and using the notion of treelike decompositions, it is sometimes possible to further decompose said parts in a canonical fashion.
Such canonical decompositions find their application in algorithms for the graph isomorphism problem. I will describe how they can be used to test isomorphism
of graphs of bounded rank width (or equivalently of bounded clique width) in polynomial time.

Contact

Christina Fries
--email hidden
passcode not visible
logged in users only

Christina Fries, 02/11/2016 21:57
Christina Fries, 12/15/2015 14:54
Christina Fries, 12/14/2015 11:50 -- Created document.