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).