research
∙
05/06/2023
Minimum-Membership Geometric Set Cover, Revisited
We revisit a natural variant of geometric set cover, called minimum-memb...
share
research
∙
03/14/2023
FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
Clustering with capacity constraints is a fundamental problem that attra...
research
∙
12/21/2022
Edge separators for graphs excluding a minor
We prove that every n-vertex K_t-minor-free graph G of maximum degree Δ ...
research
∙
01/10/2022
Detours in Directed Graphs
We study two "above guarantee" versions of the classical Longest Path pr...
research
∙
12/13/2021
How to Find a Good Explanation for Clustering?
k-means and k-median clustering are powerful unsupervised machine learni...
research
∙
11/28/2021
Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
We design the first subexponential-time (parameterized) algorithms for s...
research
∙
10/19/2020
EPTAS for k-means Clustering of Affine Subspaces
We consider a generalization of the fundamental k-means clustering for d...
research
∙
06/28/2020
A Polynomial Kernel for Line Graph Deletion
The line graph of a graph G is the graph L(G) whose vertex set is the ed...
research
∙
01/13/2020
Packing and covering balls in graphs excluding a minor
We prove that for every integer t> 1 there exists a constant c_t such th...
research
∙
12/22/2019
The shortest disjoint paths problem
For any fixed k, we show the existence of a polynomial-time algorithm de...
research
∙
11/09/2019
A Polynomial Kernel for Paw-Free Editing
For a fixed graph H, the H-free-editing problem asks whether we can modi...
research
∙
07/01/2019
The directed 2-linkage problem with length constraints
The weak 2-linkage problem for digraphs asks for a given digraph and ve...
research
∙
04/17/2018