Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 01 octobre 2019 à 14h00 en B107, Mamadou Moustapha Kanté nous parlera de : Algorithms listing combinatorial objects from graph theory

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 30 September 2019 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr