114 citations · 306 across the 50 of their papers we have counts for
4 papers · 1 filter
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
Fabrizio Grandoni, Stefan Kratsch, Andreas Wiese
The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+eps)-approximations in f(k,eps)n^{O(1)} time where k is some…
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 adaptive algorithms for maximum matching
Falko Hegerfeld, Stefan Kratsch
In the fundamental Maximum Matching problem the task is to find a maximum cardinality set of pairwise disjoint edges in a given undirected graph. The fastest algorithm for this pro…
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…