Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

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
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