Résumé : Pour une famille d'objets combinatoires $C$ (donnée souvent sous forme d'un oracle), le problème de génération consiste à lister tous les objets de $C$ sans duplicats. Cela peut être lister tous les graphes series-parallèles de taille $n$ donnée, ou encore, lister tous les ensembles satisfaisant une certaine propriété (par exemple les stables d'un graphe donné). On souhaite mesurer la complexité en temps de tels algorithmes de génération exhaustive, mais puisque les objets à lister sont souvent en quantité exponentielle par rapport à la taille de l'oracle, on est intéressé par des algorithmes de temps polynomial en les tailles cumulatives des entrées et sorties (complexité dite "output-sensitive"). L'exposé portera sur les différentes problématiques associées à ces questions et considérera deux familles de problèmes : sous-graphes maximaux satisfaisant une propriété et les transversaux minimaux.

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr