Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes

Rémi Watrigant 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms.
Document type :
Complete list of metadatas
Contributor : Abes Star <>
Submitted on : Monday, March 13, 2017 - 5:58:06 PM
Last modification on : Wednesday, January 23, 2019 - 1:52:02 PM
Long-term archiving on : Wednesday, June 14, 2017 - 3:15:22 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01488596, version 1



Rémi Watrigant. Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes. Géométrie algorithmique [cs.CG]. Université Montpellier II - Sciences et Techniques du Languedoc, 2014. Français. ⟨NNT : 2014MON20100⟩. ⟨tel-01488596⟩



Record views


Files downloads