|
Evènement pour le groupe Graphes et Logique
Date | 2012-04-10 11:00-12:00 |
Titre | Largeur 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. |
Lieu | salle 76 |
Orateur | Yann Strozecki |
Email | strozecki@logique.jussieu.fr |
Url | LRI, Paris-Sud 11 |
Aucun document lié à cet événement. RetourRetour à l'index
| |