MASCOTTE no longer exists => visit the new COATI project-team
 


Seminaire MASCOTTE
Un algorithme FPT simple exponentiel pour le problème Planar-F deletion

par Christophe Paul


Date :13/09/12
Time :10:30
Location :Euler Violet


Â' Soit F une famille de graphes. Le problÃ'¨me
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  F-deletion consiste Ã'  tester s'il est possible de
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  supprimer
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  un ensemble d'au plus k sommets dans un graphe G pour
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  obtenir un graphe H ne contenant pas de mineurs
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  issus de F. Le cas F={K_2} correspond au problÃ'¨me
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  Vertex Cover et F={K_3} Ã'  Feedback Vertex Set. Si la
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  famille
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  F contient au moins un graphe planaire le problÃ'¨me est
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  nommÃ'© Planar-F-Deletion. Nous proposons un
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  algorithme FPT en simple exponentiel (i.e. en
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  $c^{O(k)}.n^{O(1)}$) pour Planar-F-deletion. Notre
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  algorithme
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  utilise la compression itÃ'©rative, des rÃ'¨gles de
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  branchement et de rÃ'©ductions de protrusions. Le coeur de
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  notre mÃ'©thode est le calcul efficace d'une
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  dÃ'©composition en protrusions (une dÃ'©composition
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  utilisÃ'©e dans
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  de nombreux rÃ'©sultats). Nous prÃ'©senterons l'algorithme
Â' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚' Ã‚'  et parlerons de ces consÃ'©quences.



Page des séminaires