3 citations · 3 across the 2 of their papers we have counts for
4 papers
Approximate Turing Kernelization for Problems Parameterized by Treewidth
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An -approximate Turing kernel for a parameterized…
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for N…
On Kernelization for Edge Dominating Set under Structural Parameters
Eva-Maria C. Hols, Stefan Kratsch
In the NP-hard Edge Dominating Set problem (EDS) we are given a graph and an integer , and need to determine whether there is a set of at most edges…
Smaller parameters for vertex cover kernelization
Eva-Maria C. Hols, Stefan Kratsch
We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Strømme [WG 2016] who gave a ke…