Résumé de séminaire

Résumé :

Les notions de decomposition arborescente et de largeur arborescente (treewidth) ont ete introduites par Robertson et Seymour au debut des annees 80 dans le contexte de la theorie des graphes : il s'agissait de generaliser un theoreme de Kruskal. Tres vite les algorithmiciens ont compris l'interet de ces notions : plus la largeur arborescente d'un graphe est petite, plus ce graphe ressemble a un arbre. Il a ete constate assez tot que si une classe de graphes a une largeur arborescente bornee, certains problemes NP-difficiles deviennent polynomiaux voire lineaires sur cette classe, par exemple le probleme du stable maximum, l'arbre de Steiner ou l'hamiltonicite.

Lors de l'expose, j'illustrerai cette notion de decomposition arborescente et ferai le lien avec les triangulations minimales (par inclusion) des graphes. Un graphe est triangule si tout cycle de longueur superieure ou egale a quatre possede une corde, i.e. une arete entre deux sommets non consecutifs du cycle. Une triangulation d'un graphe consiste a ajouter des aretes a ce graphe pour le rendre triangule.

Je donnerai une caracterisation globale des triangulation minimales faisant intervenir les separateurs minimaux du graphe. Ensuite, je definirai la notion de clique maximale potentielle et montrerai comment ces objets permettent de calculer la largeur arborescente du graphe. J'indiquerai ensuite comment on peut enumerer ces cliques maximales potentielles en temps polynomial en leur nombre et je concluerai par des problemes ouverts.

Références :

Ma page web : http://www.ens-lyon.fr/~vbouchit/