Evènement pour le groupe Graphes et Logique


Date 2012-04-10  11:00-12:00
TitreLargeur de décomposition d'hypergraphe 
RésuméDans cet exposé, je vais présenter une décomposition arborescente d'hypergraphe. Cette notion est très simple et généralise notamment des notions de décomposition sur les matroïdes. On va montrer certaines propriétés de cette décomposition par rapport à divers opérations sur les hypergraphes ainsi que des exemples d'hypergraphes qui ont une petite ou une grande largeur. Par ailleurs, cette décomposition admet plusieurs restrictions intéressantes, et sur les graphes elle est équivalente à la largeur de clique. Enfin, on s'intéressera au problème de trouver en temps polynomial de bonnes décomposition pour des hypergraphes.  
Lieusalle 76 
OrateurYann Strozecki 
Emailstrozecki@logique.jussieu.fr 
UrlLRI, Paris-Sud 11 



Aucun document lié à cet événement.

Retour
Retour à l'index