V. D. dos Santos

activity

20182024

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2022

Reducing the Vertex Cover Number via Edge Contractions

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +2

The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and two integers $k$ and $d$ , and asks whether one can contract at most $k$ edges to reduce the size of a min…

cs.DS2020

On structural parameterizations of the selective coloring problem

Guilherme C. M. Gomes, Vinicius F. dos Santos

In the Selective Coloring problem, we are given an integer $k$ , a graph $G$ , and a partition of $V (G)$ into $p$ parts, and the goal is to decide whether or not we can pick exactly…

cs.DS2018

Dual parameterization of Weighted Coloring

Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima +3

Given a graph $G$ , a proper $k$ -coloring of $G$ is a partition $c = (S_{i})_{i \in [1, k]}$ of $V (G)$ into $k$ stable sets $S_{1}, \dots, S_{k}$ . Given a weight function $w: V(G) \to \ma…