Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 7 Décembre 2010

Acyclicité des hypergraphes et complexité

par David Duris ()

Plusieurs notions non-équivalentes généralisent l'acyclicité des graphes aux hypergraphes : la Berge-acyclicité, la gamma-acyclicité, la beta-acyclicité et l'alpha-acyclicité. Elles sont issues principalement de la théorie des bases de données mais sont étudiées dans d'autres domaines comme la combinatoire et la logique. On présente chacune de ces notions en insistant sur leur complexité. On regarde plus en détail la complexité des problèmes de décision suivants : l'existence d'un sous-hypergraphe acyclique couvrant et d'un sous-hypergraphe acyclique ayant un nombre donné d'hyperarêtes. La complexité de ces problèmes dépend du type d'acyclicité considéré et de la taille des hyperarêtes.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr