Showing 2022 · cs.DSShow all
3 papers · 2 filters
cs.DS2022
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
Johannes Blum, Yann Disser, Andreas Emil Feldmann +2
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system with two families of subsets of .…
cs.DS2022
Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
François Dross, Krzysztof Fleszar, Karol Węgrzycki +1
In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that con…
cs.DS2022
Dynamic data structures for parameterized string problems
Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki +2
We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a…