research
∙
08/17/2023
Computing complexity measures of degenerate graphs
We show that the VC-dimension of a graph can be computed in time n^log d...
share
research
∙
05/16/2023
Decomposition of (infinite) digraphs along directed 1-separations
We introduce torsoids, a canonical structure in matching covered graphs,...
research
∙
11/23/2021
Harmless Sets in Sparse Classes
In the classic TARGET SAT SELECTION problem, we are asked to minimise th...
research
∙
03/05/2020
Optimal Discretization is Fixed-parameter Tractable
Given two disjoint sets W_1 and W_2 of points in the plane, the Optimal ...
research
∙
07/04/2019