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