Evènement pour le groupe GT Graphes et Applications


Date 2010-04-09  14:00-15:00
TitreNP-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.  
LieuSalle 178 
OrateurPascal Ochem 
UrlLRI 



Aucun document lié à cet événement.

Retour
Retour à l'index