5 papers · 1 filter
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…
Approximating -Covering
Tim A. Hartmann, Tom JanÃen
-Covering, for some covering range , is a continuous facility location problem on undirected graphs where all edges have unit length. The facilities may be positioned on…