Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2024
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…
cs.DS2024
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…