LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » 链接 » 巴黎六大计算机科学实验室日志

APRRSS

F-M-DELETION paramétré par la largeur arborescente.


2017-10-13
报告人 : Julien Baste (ATER LIP6)
Résumé: Étant donnée une collection de graphes F, le problème de F-M-DELETION consiste, étant donnés un graphe G=(V,E) et un entier k, à décider s'il existe un ensemble S de sommets de G de taille au plus k tel que G privé des sommets de S ne contienne aucun graphe de F comme mineur. Ce problème est une généralisation de problèmes plus classiques tels que VERTEX COVER (F={K_2}), FEEDBACK VERTEX SET (F={K_3}), ou VERTEX PLANARIZATION (F={K_5, K_{3,3} }). Nous nous intéressons à la complexité paramétrée du problème F-M-DELETION lorsque le paramètre est la largeur arborescente de G (noté tw). Notre objectif est de déterminer, pour chaque famille F, quelle est la plus petite fonction f tel que F-M-DELETION puisse être résolu en temps f(tw)*poly(n) sur un graphe à n sommets.
Durée: 50 min + questions
更多具体信息
Romain.Demangeon (at) nulllip6.fr
 Mentions légales
网站导航 |