Showing 2019Show all
2 papers · 1 filter
cs.CC2019
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for N…
cs.CC2019
Parameterized Complexity of Conflict-free Graph Coloring
Hans L. Bodlaender, Sudeshna Kolay, Astrid Pieterse
Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring such that for each vertex t…