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