Evènement pour le groupe GT Graphes et Applications


Date 2014-11-28  15:15-16:15
TitreAlgorithmes de pré-traitement de graphes 
RésuméÉtant donné un problème paramétré de graphes (partition des sommets en k stables, ou en une forêt et au plus k sommets, etc), on s'intéresse à des algorithmes efficaces (i.e. polynomiaux) pour simplifier une instance de ce problème. Après avoir identifié un certain nombre de telles règles de simplification, on veut garantir l'efficacité de l'algorithme de pré-traitement correspondant, au moins sur une sous-classe de graphes (par exemple les graphes planaires). Selon le résultat voulu, on peut chercher à montrer que l'algorithme aboutit toujours au graphe vide, ce qui nous assure que la classe de graphes considérée admet toujours une solution (par exemple les graphes planaires pour le problème de 4-coloration). On peut plus généralement chercher à montrer que l'algorithme aboutit toujours à un graphe de taille bornée par une fonction de k. Ce type de résultat est intéressant en particulier pour des problèmes que l'on sait NP-durs en général. Ici, on s'intéresse au problème Feedback Vertex Set (combien de sommets doit-on enlever à un graphe pour obtenir une forêt ?) paramétré par la taille de solution (suffit-il d'enlever k sommets ?), dans le cadre des graphes planaires. On présente un algorithme de pré-traitement qui aboutit en temps linéaire à un graphe planaire de taille au plus 13k. Il s'agit d'une collaboration avec Lukasz Kowalik (Université de Varsovie).  
LieuSalle 178 
OrateurMarthe Bonamy 



Aucun document lié à cet événement.

Retour
Retour à l'index