Sujet : Algorithmes pour 3SAT et autres problèmes NP-complets

Responsable : J.M. Robson
Téléphone : 05 56 84 60 78
e-mail : robson@labri.fr
Site Web : http://dept-info.labri.u-bordeaux.fr/~robson
Equipe : Combinatoire et Algorithmique

Présentation du sujet :

On va appliquer au problème 3SAT les memes méthodes de conception et
d'analyse d'algorithmes qui ont donné l'algorithme le plus performant
connu pour le problème de recherche d'un clique maximum
(l'algorithme avec la meilleure performance prouvée dans le pire des cas).
Ces méthodes sont l'étude detaillée des configurations possibles aux
alentours d'un sommet (ou d'une variable) choisi, analyse de
l'utilitisation d'informations auxiliaires sur le sous-problème
à traiter et/ou sur les solutions qu'il faut prendre en compte,
et l'utilisation de programmation dynamique pour éviter de
traiter plusieurs fois les mêmes petits sous-problèmes.

Mot-clés : NP-complet, 3SAT, analyse d'algorithmes,

Références :

Algorithms for Maximum Independent Sets, Journal of Algorithms,
tome 7, 1986, pp.425-440.


Improved Maximum Independent Set Algorithms:
Preliminary Report, DIMACS workshop
on Faster Exact Solutions for NP-complete Problems,
http://dept-info.labri.u-bordeaux.fr/~robson/.

Finding a maximum independent set in time O(2n/4),
rapport technique 1251-01, LaBRI, à paraître.