Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The Graph Isomorphism problem: techniques from structural graph theory and canonical decompositions
Speaker:Pascal Schweitzer
coming from:RWTH Aachen University
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 16 February 2016
Duration:30 Minutes
Building:E1 4
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.
Name(s):Christina Fries
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Christina Fries, 02/11/2016 09:57 PM
  • Christina Fries, 12/15/2015 02:54 PM
  • Christina Fries, 12/14/2015 11:50 AM -- Created document.