23 citations · 60 across the 50 of their papers we have counts for
6 papers · 2 filters
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 and , a -spindle is the union of pairwise internally vertex-disjoint directed paths with arcs between two vertices $…
On the (parameterized) complexity of recognizing well-covered (r,l)-graphs
Sancrey R. Alves, Konrad K. Dabrowski, Luerbio Faria +3
An -partition of a graph is a partition of its vertex set into independent sets and cliques. A graph is if it admits an -partition.…
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Julien Baste, Didem Gözüpek, Christophe Paul +3
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirect…
Hitting minors on bounded treewidth graphs. I. General upper bounds
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos
For a finite collection of graphs , the -M-DELETION problem consists in, given a graph and an integer , deciding whether there exists …
Ruling out FPT algorithms for Weighted Coloring on forests
Júlio Araújo, Julien Baste, Ignasi Sau
Given a graph , a proper -coloring of is a partition of into stable sets . Given a weight function $w: V(G) \to \ma…
Complexity Dichotomies for the Minimum F-Overlay Problem
Nathann Cohen, Frédéric Havet, Dorian Mazauric +2
For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V(H) is equal to V(G) and the subgraph of G induced by every hyperedge of…