Liste des événements uniques du groupe Séminaire-Ecole sur les décompositions des graphes


2008-04-03Large rank-width and circle graphs as vertex-minors
14:00-15:30
Amphi LaBRI
Résumé plus précis et RAPPEL

L'inclusion des graphes au sens des "vertex-minors" est une notion analogue à
l'inclusion au sens des mineurs, tout comme la largeur de rang ("rank-width")
est analogue à la largeur arborescente.
On conjecture que les graphes d'intersection des cordes d'un cercle ("circle graph") jouent , par rapport à la largeur de
rang, un rôle
semblable à celui des graphes planaires par rapport à la largeur arborescente, et que les graphes
qui ne contiennent pas comme "vertex minor " un graphe d'intersection de cordes donné
sont de largeur de rang bornée.
Ce résultat généraliserait "Graph Minors V".
Il est montré dans l'exposé pour les "line graphs" (graphes d'incidences) et les graphes d'intersection
de cordes bipartis.
La conjecture reste ouverte.

Résumé fait par B. Courcelle
 Plus d'infos  


2008-02-20Comptages de graphes planaires et plus
14:00-16:00
075
Suite de l exposé du 14

SALLE 75 (oubli du précédent courrier)
 Plus d'infos  


2008-02-14Comptage de graphes planaires, ou à mineurs exclus.
15:15-16:30
076
RAPPEL: Exposé de Mireille
Bousquet Mélou
--
Le 3 Avril : S. OUM
 Plus d'infos  


2008-01-24Ordre de minoration pour larg. arbo. bornée
15:15-17:00
Amphi LaBRI
Exposé de Graph Minors IV
article de Robertson et Seymour
 Plus d'infos  


2007-11-29Largeurs de clique et de rang (suite)
14:00-15:30
Amphi LABRI
Suite de l'exposé du 18 octobre
(désolé pour l intervalle important)
 Plus d'infos  


2007-11-29Largeurs de clique et de rang ; algorithmes
14:00-15:30
Amphi LaBRI
Décompositions de Graphes :
Comparaison des Largeur arborescente et Largeurs de Clique et de Rang.

Plus précisément :
Algorithmes FPT
"Parsing" : recherche de décompositions
"grammaires algébriques de graphes" définies comme des systèmes d'équations.

La première partie a été exposée le 18 octobre.

----------
Les transparents de l'exposé de P Ossona de Mendez sont en ligne sur :
http://www.labri.fr/perso/courcell/SeminaireDecGraphes/ExpoPOM.pdf
 Plus d'infos  


2007-11-22Patrice Ossona de Mendez
14:00-17:00
Amphi LABRI
Exposé double Séminaire + groupe de travail
Titre et résumé à
préciser
 Plus d'infos  


2007-10-18Programme 2007-2008 + Largeur de clique
14:00-15:30
Amphi LABRI
Proposition de thèmes d'exposés (20 minutes) ;
Largeur de clique et notions équivalentes (1h)
 Plus d'infos  


2007-04-19Décompositions en Coupes et GRAAL
14:00-15:30
Salle 076
Présentation de la "split decomposition" de Cunnigham nommée en bon français "décomposition en coupe".
Compte rendu de la réunion du projet GRAAL à Montpellier 2-4 avril
 Plus d'infos  


2007-03-22Décompositions modulaire et
14:00-16:00
76
Pour changer des décompositions arborescentes, je parlerai des décompositions modulaires (Gallai 1967 et bien d'autres depuis), de la "split decomposition" de Cunnigham (1982) et des applications sur la structure des graphes. Les définitions figurent dans mes articles http://www.labri.fr/perso/courcell/Textes/MSOL16(2006).pdf

http://www.labri.fr/perso/courcell/Textes/BC-Delhom-submitted-2005.pdf

(Je n'ai pas l'intention d'exposer en 1 heure la centaine de pages indiquée).
 Plus d'infos  


2007-03-08Routage et distances dans les graphes de largeur arborescente bornée.
14:00-15:30
076
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éarchiques" pour les graphes de largeur arborescente
bornée, outils précieux pour beaucoup d'autres problèmes
 Plus d'infos  


2007-02-08Exploration de graphes et décompositions arborescentes
15:45-17:15
AMPHI Labri
Étant donné un graphe fini G, on peut définir un jeu de gendarmes et de voleurs
sur les sommets de G. À chaque tour, les gendarmes peuvent placer un nouveau
gendarme ou retirer un gendarme d'un sommet du graphe. Le voleur peut se
déplacer sur n'importe quel sommet accessible depuis sa position actuelle
sans rencontrer de gendarme.
Si on cherche une stratégie gagnante pour les gendarmes, on cherche le nombre
minimal de gendarmes nécessaires pour attraper le voleur. Or ce nombre est lié
à la largeur arborescente du graphe.
Inversement, si on cherche une stratégie pour le voleur, on obtient une
obstruction à l'existence d'une décomposition arborescente: les
enchevêtrements. Cette obstruction permet de démontrer simplement que la
largeur arborescente d'une grille nxn est n.

 Plus d'infos  


2006-12-14Métaheuristique du Voyageur de Commerce
15:15-16:30
076
Un grand nombre d'heuristiques pour résoudre des problèmes
d'optimisation combinatoire utilisent des choix aléatoires. Ainsi, ce
genre d'heuristique produisent 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.
 Plus d'infos  


2006-11-23Décompositions arborescentes (II)
14:00-15:15
076
Décompositions linéaires, nombres de Strahler, chirugie des dec. arbo., décompositions en composantes 2- et 3-connexes. Les propriétés inductives sont renvoyées à plus tard.
 Plus d'infos  


2006-11-16Déompositions arborescentes (I)
15:15-15:30
076
 Plus d'infos  




Liste des événements répétitifs du groupe Séminaire-Ecole sur les décompositions des graphes




Retour
Retour à l'index