logo labri

 

 

Séminaire – Ecole  "Décomposition des Graphes et Applications"

Responsables : Bruno Courcelle, Cyril Gavoille, Frédéric Mazoit

Certains jeudis à 14h00  (ou  15h15) - salle 076-  (rez-de-chaussée du LaBRI) - Université Bordeaux 1


Documents en ligne relatifs au thème du séminaire :

 

B. Courcelle, Décompositions arborescentes, mai 2006, chapitre d’un ouvrage à paraître, Editions Hermès.

 

F. Mazoit : Explorations de graphes et enchevêtrements (« brambles »).

 

C. Gavoille : Routage dans les graphes k-séparables.

 

 

Articles de chercheurs hors du LaBRI :

 

P. Ossona de Mendez : Transparents de l’exposé du 22 novembre 2007-11-26

 

H. Bodlaender : éminent spécialiste de la largeur arborescente :
http://www.cs.uu.nl/research/techreps/aut/hansb.html

 

NOUVEAU : P. Hlineny, S. Oum, D. Seese, G. Gottlob : Width parameters beyond tree-width and their applications, Mai 2006.

 

 


Exposés faits ou à  venir :

 

Exposés ultérieurs, dates à préciser :

            C. Gavoille : Graphes excluant comme mineur un graphe donné : présentation d’un résultat de Robertson et Seymour, et ses applications.

            Résultats et problèmes ouverts en matière de comptage de graphes.

            Routage et distances approchées dans les graphes planaires

            Largeur arborescente et algèbre linéaire.

            B. Courcelle : « Local bounded tree-width » d’après Eppstein, Frick, Grohe.


Exposés Passés :

 

Année 2007

(Transparents en ligne, voir ci-dessus).

Dans cette leçon, j'expliquerai comment les décompositions arborescentes
peuvent servir aux calculs de routes et de distances dans les graphes.
Pour cela, je détaillerai les notions de "séparateurs" et de
"décompositions hiérarchiques" pour les graphes de largeur arborescente
bornée, outils précieux pour beaucoup d'autres problèmes

Année 2006

Résumé pour le 14 12 : Un grand nombre d'heuristiques pour résoudre des problèmes
d'optimisation combinatoire utilisent des choix aléatoires. Ainsi, ce
genre d'heuristique produit un grand nombre de solutions approchées
et on ne retient usuellement que la meilleure. On peut cependant se dire
qu'en combinant plusieurs résultats, il doit être possible d'obtenir un
résultat encore meilleur. Les travaux que je vais présenter (dû à W.
Cook et P. Seymour) partent de ce principe là pour construire une
meta-heuristique pour le voyageur de commerce basée sur l'utilisation
des décompositions arborescentes.

(Transparents en ligne).