Responsable: J.M. Robson
LaBRI, 05 40 00 60 78; robson@labri.u-bordeaux.fr
Équipe de recherche: Combinatoire et Algorithmique Distribuée
Titre du sujet: Bornes supérieures sur le temps de calcul
dans le pire cas d'algorithmes pour quelques problèmes NP-difficiles
Présentation:
Les algorithmes avec la meilleure performance démontrée
(dans le pire des cas) pour quelques problèmes NP-complets
(tels clique, ensemble indépendant) sont récursifs et
dépendent de bien choisir un sommet où on va brancher
selon la structure locale du graphe autour de ce sommet.
La démonstration d'une bonne borne supérieure sur le temps
de calcul utilise:
(1) des analyses détaillées des appels récursifs possibles en
certains cas importants
(a) sommets de bas degré
(b) des cas où il suffit de considérer des ensembles qui
vérifient une condition spécifique
(2) analyse de l'utilité de
la programmation dynamique pour éviter de faire plusieurs fois
le même calcul sur de petits sous-graphes induits
(3) énumération et analyse automatisée des configurations
possibles autour d'un sommet de degré donné
Quelques possibilités de poursuite de ce travail sont:
(1) Etendre (peut-être de façon ad hoc mais de
préférence systématiquement) l'étude des cas où
l'ensemble doit vérifier une condition à des cas de
plusieurs conditions simultanées
(2) Améliorer les bornes supérieures sur le nombre de
petits sous-graphes induits générés
(3) Traitement plus efficace des configurations possibles autour
d'un sommet afin de pouvoir traiter des boules plus larges
(4) Application des mêmes méthodes à d'autres problèmes
Références:
Computers and Intractability, Garey et Johnson.
http://1013seopc.eecs.uic.edu/FESNP/program.html
et les liens de cette page:
http://dept-info.labri.u-bordeaux.fr/~robson/mis/