Abstract (FR)

Cette thèse se situe à l'interface entre deux branches de la théorie de la complexité, la résolution exacte et l'approximation polynomiale. Nous développons dans un premier temps des algorithmes modérément exponentiels, capables de résoudre des problèmes fondamentaux de théorie des graphes (stable maximum, stable dominant mi-nimal, clique dominante, quasi-stable) de façon plus rapide que ceux existant jusqu'ici. Surtout, nous introduisons la notion d' approximation exponentielle , et exhibons des algorithmes exponentiels à garantie de performance plus rapides que les algorithmes exacts pour une large variété de problèmes classiques, parmi lesquels : stable maximum, domination, coloration de sommets ou d'arêtes, voyageur de commerce, arbre de Steiner. . .