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.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |