Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
FPT Parameterisations of Fractional and Generalised Hypertree Width
Matthias Lanzinger, Igor Razgon, Daniel Unterberger
We present the first fixed-parameter tractable (FPT) algorithms for exact computation of generalized hypertree width (ghw) and fractional hypertree width (fhw). Our algorithms are…
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…