Victor A. Campos

activity

20072023

most citedPolyhedral studies of vertex coloring problems: The asymmetric representatives formulation

3 citations · 6 across the 10 of their papers we have counts for

collaborators

Showing cs.DSShow all

6 papers · 1 filter

cs.DS2021

Parameterized complexity of computing maximum minimal blocking and hitting sets

Júlio Araújo, Marin Bougeret, Victor A. Campos +1

A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$ . Let $mmbs (G)$ be the size of a maximum (inclusion-wise) minimal bl…

cs.DS2021

Introducing lop-kernels: a framework for kernelization lower bounds

Júlio Araújo, Marin Bougeret, Victor A. Campos +1

In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph $G$ and a positive integer $k$ , and the objective is to decide whether $G$ contains a minimal vertex cover…

cs.DS2020

Adapting the Directed Grid Theorem into an FPT Algorithm

Victor Campos, Raul Lopes, Ana Karolinna Maia +1

The Grid Theorem of Robertson and Seymour [JCTB, 1986], is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of a…

cs.DS2020

Edge-Disjoint Branchings in Temporal Graphs

Victor Campos, Raul Lopes, Andrea Marino +1

A temporal digraph $G$ is a triple $(G, γ, λ)$ where $G$ is a digraph, $γ$ is a function on $V (G)$ that tells us the timestamps when a vertex is active, and $λ$ is a functio…

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…

cs.DS2017

On the complexity of finding internally vertex-disjoint long directed paths

Júlio Araújo, Victor A. Campos, Ana Karolinna Maia +2

For two positive integers $k$ and $ℓ$ , a $(k \times ℓ)$ -spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $ℓ$ arcs between two vertices $…