Fedor V. Fomin

Protrusions in graphs and their applications

The Vienna Center for Logic and Algorithms hosted a talk by Fedor V. Fomin at WorKer 2011 – The Third Workshop on Kernelization.

DATE:Friday, September 2, 2011
TIME:09:00 – 10:00
VENUE:Vienna University of Technology, EI 9 Hlawka Hörsaal (Gußhausstrasse 25-29, ground floor)


A protrusion in a graph is a subgraph of constant treewidth that can be separated from the graph by removing a constant number of vertices. We discuss combinatorial properties of graphs implying existence of large protrusions and give a number of algorithmic applications of protrusions.

Given at WorKer 2011 – The Third Workshop on Kernelization (slides are linked there).

Comments are closed.