MASCOTTE no longer exists => visit the new project-team
Internship MASCOTTEPathwidth des graphes planaires extérieurs 2-connectés
by Henry Wei Cheng HSU
| | | | Advisor | David Coudert et Nicolas Nisse | | School | Ecole Polytechnique | | Degree | 3eme année Polytechnique | | Period | 15/04/10-31/08/10 | | Report | Available in pdf  |
La pathwidth et la treewidth des graphes ont été beaucoup étudiées <br />à cause de leurs importants aspects structurels et algorithmiques. Certains problèmes qui sont NP-complets en général peuvent être résolus de manière efficace dans la classe des graphes de treewidth et pathwidth bornées. La résolution est basée sur la décomposition en arbre et en chemin, qui sont les aspects constructives de la treewidth et de la pathwidth, respectivement. <br />La détermination de ces paramètres est NP-complet en général, pourtant elle peut devenir polynomiale pour certaines classes de graphes. En particulier, des algorithmes efficaces ont été proposés pour le calcul de la pathwidth dans la classe des arbres. Skodinis [11] (2000) a proposé un algorithme linéaire pour cette question. Pour la classe des graphes planaires extérieurs 2-connectés un <br />algorithme en O(n^11 ) existe mais il est inefficace et impraticable. <br />La pathwidth a été aussi étudiée pour sa relation avec les jeux de recherche en graphes. Familièrement, ces jeux visent à déterminer le nombre minimum d'agents nécessaires pour capturer un fugitive dans un graphe. Dans le cas d'un fugitive invisible, la valeur ns(G) (node search number) est la quantité minimum d'agents requise pour la capture. Il est montré que la pathwidth d'un graphe G <br />est égale à ns(G)-1. <br />Dans ce rapport on utilise l'interprétation des jeux de recherche pour l'élaboration d'un algorithme pour le calcul de la pathwidth des graphes planaires extérieurs 2-connectés. Dans ce stage, nous avons obtenu des résultats préliminaires pour cette étude. En particulier, deux théorèmes obtenus sont un pas important <br />pour le développement d'un algorithme pratique et efficace pour cette classe de graphes.
List of interships | 
