Evènement pour le groupe GT Graphes et Applications


Date 2013-06-14  14:00-15:00
TitreOrientations "k-faibles" : un résultat de complexité 
RésuméUne orientation d'un graphe non orienté G est k-faible si pour toute paire de sommets {u,v} de G il existe un chemin de longueur au plus k reliant u et v dans n'importe quel sens. Durant cet exposé, nous montrerons que déterminer si un graphe non orienté admet une orientation k-faible est un problème NP-complet pour tout k>=2. La NP-complétude du problème où k=2 implique qu'il est NP-complet de déterminer si un graphe non orienté est l'équivalent d'une clique pour la coloration orientée des graphes non orientés, i.e. si son nombre chromatique orienté vaut exactement son ordre. Travail réalisé en collaboration avec R. Duvignau et S. Kirgizov.  
LieuSalle 178 
OrateurJulien Bensmail 



Aucun document lié à cet événement.

Retour
Retour à l'index