3 papers
cs.DS2020
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
Carl Einarson, Gregory Gutin, Bart M. P. Jansen +2
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the -Edge-Connected and -Vertex-Connected VC problem (where is a fixe…
cs.DS2020
A general kernelization technique for domination and independence problems in sparse classes
Carl Einarson, Felix Reidl
We unify and extend previous kernelization techniques in sparse classes [6,17] by defining water lilies and show how they can be used in bounded expansion classes to construct line…
cs.DS2019
Domination above r-independence: does sparseness help?
Carl Einarson, Felix Reidl
Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound…