 |
 |
|
Liste des événements uniques du groupe Séminaire-Ecole sur les décompositions des graphes
| 2008-04-03 | Large 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-20 | Comptages 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-14 | Comptage 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-24 | Ordre 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-29 | Largeurs 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-29 | Largeurs 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-22 | Patrice 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-18 | Programme 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-19 | Dé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-22 | Dé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-08 | Routage 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-08 | Exploration 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-14 | Mé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-23 | Dé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-16 | Dé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
RetourRetour à l'index
| |