-
Graphs decompositions: some limites and obstructions
Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these... -
Parameterized Complexity of Connected Even/Odd Subgraph Problems
International audience -
Lower Bounds on the Complexity of MSO_1 Model-Checking
International audience -
Tractability and approximability of maximal strip recovery
International audience -
A linear kernel for planar red-blue dominating set
International audience -
Steiner Problems with Limited Number of Branching Nodes
International audience -
Catalan structures and dynamic programming in H-minor-free graphs
JCSS Special Issue: Cloud Computing 2011 -
Optimization problems with propagation in graphs : Parameterized complexity a...
In this thesis, we investigate the computational complexity of optimization problems involving a “diffusion process” in a graph. More specifically, we are first...
