Ioan Todinca (LIP, ENS Lyon)

Robertson et Seymour ont defini la decomposition arborescente des graphes quelconques dans une etude combinatoire de theorie des graphes.

Mais la decomposition arborescente est un concept interessant pour l’algorithmique des graphes. Donner une decomposition arborescente d’un graphe consiste a representer ce graphe comme un arbre generalise, d’une certaine largeur. Il a ete montre que beaucoup de problemes NP-difficiles deviennent polynomiaux pour des graphes de largeur arborescente (treewidth) bornee. J’introduirai ces notions et je montrerai comment resoudre le probleme du stable maximum pour des graphes de largeur arborescente bornee.

Je m’interesserai ensuite a des classes de graphes pour lesquelles la largeur arborescente est calculable en temps polyonmial - sachant que le calcul de ce parametre est NP-difficile pour des graphes quelconques. Nous verrons que le calcul de la largeur arborescente passe par la connaissance des separateurs minimaux du graphe, ainsi que d’un objet que nous avons introduit, a savoir les cliques maximales potentielles.