Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 16 Février 1999

Decompositions arborescentes des graphes

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr