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/