Algorithmes exacts et exponentiels sur les graphes : énumération, comptage et optimisation
Institution:
Université de LorraineDisciplines:
Directors:
Abstract EN:
The assumption that many problems do not admit algorithm (exact and deterministic) polynomial ate of the advent of the theory of NP-completeness in the 70s. Since many theories and algorithmic techniques have been developed to solve these problems difficult as efficiently as possible. In this thesis, we focus on exact algorithms weakly exponential. The objective is to obtain algorithms complexity 0 * (c ^ n) where n is the size of the data and one constant c as small as possible
Abstract FR:
L'hypothèse qu'un grand nombre de problèmes n'admettent pas d'algorithme (exact et déterministe) polynomial date de l'avènement de la théorie de la NP-complétude dans les années 70. Depuis, de nombreuses théories et techniques algorithmiques se sont développées pour résoudre ces problèmes difficiles le plus efficacement possible. Dans cette thèse, nous nous intéressons aux algorithmes exacts faiblement exponentiels. L'objectif est d'obtenir des algorithmes de complexité 0* (c^n) où n est la taille de la donnée et c une Constante la plus faible possible