4 papers · 1 filter
Computing Twin-Width via Treedepth and Vertex Integrity
Robert Ganian, Mathis Rocton
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorith…
Polynomial kernels for edge modification problems towards block and strictly chordal graphs
Maël Dumas, Anthony Perez, Mathis Rocton +1
We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph and an integer and seeks to…
The Parameterized Complexity Landscape of the Unsplittable Flow Problem
Robert Ganian, Mathis Rocton, Daniel Unterberger
We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph…
Twin-Width Meets Feedback Edges and Vertex Integrity
Jakub Balabán, Robert Ganian, Mathis Rocton
The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towar…