J. Araújo

activity

20152023

collaborators

Showing 2017Show all

2 papers · 1 filter

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 $…

cs.DS2017

Ruling out FPT algorithms for Weighted Coloring on forests

Júlio Araújo, Julien Baste, Ignasi Sau

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…