Accueil | Membres | Projets et collaborations | Séminaire et groupe de travail

Le séminaire/groupe de travail VAG a lieu le jeudi de 10h à 11h (et quelques) en salle E.323.

Pavol Hell
Graphs and Polymorphisms

Polymorphisms are useful in logic and algebra, and seem the right tool for solving constraint satisfaction problems. I will illustrate their use in graph theory by characterizing interesting old and new graph classes.

Thomas Erlebach
Domination in geometric intersection graphs
This is joint work with Erik Jan van Leeuwen.

Dominating set problems in geometric intersection graphs can be motivated by routing backbone construction problems in wireless ad-hoc networks. For intersection graphs of disks and other fat objects, existing approximation techniques do not seem to be able to handle the dominating set problem except in the special case of unit-size objects. We present approximation algorithms and inapproximability results that shed new light on the approximability of the dominating set problem in geometric intersection graphs. On the one hand, we show that for intersection graphs of arbitrary fat objects, the dominating set problem is as hard to approximate as for general graphs. For intersection graphs of arbitrary rectangles, we prove APX-hardness. On the other hand, we present a new general technique for deriving approximation algorithms for various geometric intersection graphs, yielding constant-factor approximation algorithms for $r$-regular polygons, where $r$ is an arbitrary constant, and for rectangles with bounded aspect ratio. For arbitrary fat objects with bounded ply, we get a $(3+\epsilon)$-approximation algorithm.

Michel Habib
Some new and old results on simplicial elimination scheme on chordal and interval graphs

In this talk we study again these central objects which appear to be important for the structural analysis of chordal graphs. We provide some new properties of maximal clique trees, which lead to interesting algorithmic problems.
Finally we describe and prove in this context an old algorithm M.H, C. Paul R. McConnell (2000) for interval graph recognition.

Binh-Minh Bui Xuan
Représentation arborescente de familles d'ensembles et applications en décomposition de graphes et en algorithmique de graphes
Soutenance de thèse.

Cette thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.
La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci- dessus : celle concernant les décompositions de graphes.
Enfin, la deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude. Dans chacun des trois, il sera montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace. Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.