Journée-séminaire de combinatoire

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

Le 13 mars 2012 à 13h45 en B311, Arnaud Mary nous parlera de : Génération des dominants minimaux d'un graphe

Résumé : La théorie des bases de données et la théorie des treillis présentent de nombreux liens que je rappellerai dans cette présentation. Je présenterai ensuite le problème de génération des transversaux minimaux d'un hypergraphe et j'expliquerai en quoi celui-ci est fortement lié à la théorie des treillis. Un hypergraphe H est une collection d'ensembles E (appelés hyperarête) sur un ensemble de sommet V. Un transversal de H est un ensemble de sommets qui intersecte toutes les hyperarêtes de H. Le problème de génération associé au transversaux, consiste à "lister" tous les transversaux minimaux d'un hypergraphe, c'est-à-dire ceux qui ne contiennent aucun autre transversal. Je parlerai enfin d'un cas particulier du problème de génération des transversaux minimaux qui est la génération des dominants minimaux d'un graphe.

 [Slides.pdf]


Dernière modification : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr