|
|
|
Intitulé:
NP-complétude pour les colorations impropre, orientée et acyclique du groupe GT Graphes et Applications
|
Date | 2010-04-09 14:00-15:00 |
Titre | NP-complétude pour les colorations impropre, orientée et acyclique |
Résumé | Résumé : Trois problèmes :
* Partition des sommets du graphe sont partitionnables en un stable et un graphe de degré au plus 1 :
NP-complet pour les graphes planaires de degré max 3 de maille 7.
Réduction à partir de PLANAR-(3,<=4)-SAT.
* Homomorphisme d'un graphe orienté vers T4 (le tournoi à 4 sommets contenant un circuit hamiltonien) :
NP-complet pour les graphes bipartis planaires de degré max 3 et de maille au moins k (pour tout k fixé).
Réduction à partir de PLANAR-(3,<=4)-SAT.
* Coloration acyclique en 4 couleurs :
NP-complet pour les graphes bipartis planaires de degré max 8.
Réduction à partir de PLANAR-3-COLORABILITY.
Les réductions de np-complétude sont souvent techniques et soporifiques, mais pas celles-la. Cela se voudra pédagogique et je pourrais sacrifier une des trois preuves si le temps manque. |
Lieu | Salle 178 |
Orateur | Pascal Ochem |
Url | LRI |
Aucun document lié à cet événement. RetourRetour à l'index
| |