3 papers
cs.DS2022
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
Jana Cslovjecsek, Michał Pilipczuk, Karol Węgrzycki
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of axis-parallel rectangles in the plane. The task is to find a subset of pairwi…
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…