5 citations · 6 across the 3 of their papers we have counts for
5 papers
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 is a subset of vertices that intersects every maximum independent set of . Let be the size of a maximum (inclusion-wise) minimal bl…
Width Parameterizations for Knot-free Vertex Deletion on Digraphs
Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro +2
A knot in a directed graph is a strongly connected subgraph of with at least two vertices, such that no vertex in is an in-neighbor of a vertex in $V(G)\setminus…
Approximation results for makespan minimization with budgeted uncertainty
Marin Bougeret, Klaus Jansen, Michael Poss +1
We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which…
(Arc-disjoint) cycle packing in tournament: classical and parameterized complexity
Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut
Given a tournament , the problem MaxCT consists of finding a maximum (arc-disjoint) cycle packing of . In the same way, MaxTT corresponds to the specific case where the colle…
Triangle packing in (sparse) tournaments: approximation and kernelization
Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut
Given a tournament T and a positive integer k, the C_3-Pakcing-T problem asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tourna…