114 citations · 306 across the 50 of their papers we have counts for
Showing 2019 · cs.DSShow all
3 papers · 2 filters
cs.DS2019
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…
cs.DS2019
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…
cs.DS2019
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…