登入選單

返回Google圖書搜尋

Algorithmes exponentiels pour la résolution exacte et approchée de problèmes NP-difficiles

Nicolas Bourgeois

出版	2009
URL	http://books.google.com.hk/books?id=nGIbtwAACAAJ&hl=&source=gbs_api

註釋

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. . .