Author
Bourgeois, Nicolas
Thesis supervisor
Paschos, Vangelis
Type
Thèse
Item number of pages
241
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. . .
Abstract (EN)
This thesis is a junction between two fields of complexity theory, namely exact computation and efficient approximation.We first design faster exponential algorithms for several NP-hard problems (maximum independent set, minimum independent dominating set, dominating clique, quasi independent set). Moreover, we introduce the "moderately exponential approximation" field, displaying fast (though exponential) approximation algorithms for many classical graph problems, such as : independent set, dominating set, edge and vertex coloring, traveling salesman, Steiner tree. . .
