4 papers
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth- Deletion
Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann +1
For a constant , Pathwidth- Deletion is the problem of deciding whether, for a given graph and integer , there is a set of size at most su…
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances
Tim A. Hartmann, Dániel Marx
The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these p…
From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs considers each edge as a continuous unit-length interval of points. In the problem -Tour defined within this model, the objective to f…
From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours -Covering All Points on All Edges
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For…