research
∙
09/01/2022
Generalized k-Center: Distinguishing Doubling and Highway Dimension
We consider generalizations of the k-Center problem in graphs of low dou...
share
research
∙
08/30/2022
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are giv...
research
∙
11/03/2021
The Parameterized Complexity of the Survivable Network Design Problem
For the well-known Survivable Network Design Problem (SNDP) we are given...
research
∙
10/21/2020
A Note on the Approximability of Deepest-Descent Circuit Steps
Linear programs (LPs) can be solved through a polynomial number of so-ca...
research
∙
06/23/2020
Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs
We study clustering problems such as k-Median, k-Means, and Facility Loc...
research
∙
06/18/2020
Parameterized Inapproximability of Independent Set in H-Free Graphs
We study the Independent Set (IS) problem in H-free graphs, i.e., graphs...
research
∙
06/08/2020
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Parameterization and approximation are two popular ways of coping with N...
research
∙
05/31/2020
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
We present a data structure that in a dynamic graph of treedepth at most...
research
∙
02/18/2020
Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
We develop an FPT algorithm and a kernel for the Weighted Edge Clique Pa...
research
∙
11/29/2019
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
(see paper for full abstract) Given a vertex-weighted directed graph G...
research
∙
10/03/2019
FPT Inapproximability of Directed Cut and Connectivity Problems
(see paper for full abstract) Cut problems and connectivity problems o...
research
∙
02/19/2019
Travelling on Graphs with Small Highway Dimension
We study the Travelling Salesperson (TSP) and the Steiner Tree problem (...
research
∙
12/20/2018
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
We consider the classic Facility Location, k-Median, and k-Means problem...
research
∙
02/23/2018
The Parameterized Hardness of the k-Center Problem in Transportation Networks
In this paper we study the hardness of the k-Center problem on inputs th...
research
∙
10/02/2017
Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
We study the Steiner Tree problem, in which a set of terminal vertices n...
research
∙
07/20/2017