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
∙
09/24/2022
When you come at the kings you best not miss
A tournament is an orientation of a complete graph. We say that a vert...
research
∙
11/23/2021
Harmless Sets in Sparse Classes
In the classic TARGET SAT SELECTION problem, we are asked to minimise th...
research
∙
02/20/2020
A general kernelization technique for domination and independence problems in sparse classes
We unify and extend previous kernelization techniques in sparse classes ...
research
∙
01/15/2020
A color-avoiding approach to subgraph counting in bounded expansion classes
We present an algorithm to count the number of occurrences of a pattern ...
research
∙
06/21/2019
Domination above r-independence: does sparseness help?
Inspired by the potential of improving tractability via gap- or above-gu...
research
∙
03/06/2019
Longest paths in 2-edge-connected cubic graphs
We prove almost tight bounds on the length of paths in 2-edge-connected ...
research
∙
05/04/2018
Lower and Upper Bound for Computing the Size of All Second Neighbourhoods
We consider the problem of computing the size of each r-neighbourhood fo...
research
∙
04/27/2018
Alternative parameterizations of Metric Dimension
A set of vertices W in a graph G is called resolving if for any two dist...
research
∙
02/27/2018
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
The notions of bounded expansion and nowhere denseness not only offer ro...
research
∙
02/16/2018
Parameterized Algorithms for Zero Extension and Metric Labelling Problems
We consider the problems ZERO EXTENSION and METRIC LABELLING under the p...
research
∙
01/15/2018