5 citations · 15 across the 12 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021
Optimization problems in graphs with locational uncertainty
Marin Bougeret, Jérémy Omer, Michael Poss
Many discrete optimization problems amount to selecting a feasible set of edges of least weight. We consider in this paper the context of spatial graphs where the positions of the…
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 is a subset of vertices that intersects every maximum independent set of . Let 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 and a positive integer , and the objective is to decide whether contains a minimal vertex cover…