Technische Universität Wien
Tuesday, May 8 at 2:30 PM
In this talk I will consider the Bounded Degree Vertex Deletion Problem. In this problem we ask for a subset of vertices in a graph, such that after deleting that set the remaining graph has bounded maximum degree. On the one hand I will show recent parametrized complexity results, showing that the problem is W-hard parametrized by most structural parameters, such as Feedback Vertex Set or Treewidth. On the other hand I present two parametrized algorithms, followed by a specialized algorithm on circle graphs. This last algorithm we successfully used to generate two-sided circular graph layouts.
Download presentation (password protected)