Théorie des graphes
Le sujet principal est une point de vue structurel et algorithmique. L'équipe a établi une expertise comprennant les problèmes tel que trouver les grands cylcles d'un graphe donné, colorier un graphe, résoudre des problèmes de couverture, ou faire avancer la théorie des graphes en trouvant les graphes extrèmes répondant à une contrainte.
La généralisation de quelques problèmes est aussi considérée pour les graphes arêtes ou sommets colorés. Par exemple, il a été étudié les graphes couvrants colorés pour des graphes arêtes ou sommets colorés. De manière alternative il a été recherche l'ensemble dominant dans un graphe ayant au moins un sommet de chaque couleur. au delà de l'intérêt purement théoriques ces démarches ont un grand intérêt aussi bien dans le domaine de la bioinformatique que dans celui du Web.
Bon nombre des questions que nous considérons peuvent aussi être déclarée en termes d'optimisation de linéaire. Ce qui ouvre des persepectives.
Nous avons de nombreuses collaborations avec les groupes français : LaBRI, LIRMM, LIAFA et LIMOS aussi bien qu'en Europe, en Amérique du nord et du sud et principalement en Asie avec la Chine, le Japan, l'Inde.
Eliminating more than vertices in graphs
summary: Considérons le jeu suivant sur un graphe. À chaque tour, le joueur peut enlever un sommet de chaque composante connexe du graphe courant. Le but du jeu est d’éliminer tous les sommets du graphe. Le nombre minimum de tours nécessaires est appelé la treedepth du graphe. C’est ...
Reconstruction de graphes via des requêtes sur les triplets
summary: Considérons un oracle disposant d'un graphe labellisé caché. L'objectif de la reconstruction de graphes est de retrouver ce graphe caché en interrogeant l'oracle avec certains types de requêtes. Les requêtes que nous examinons portent sur des triplets de sommets du graphe, plus précisément, sur la structure ...
Fractional domatic number and minimum degree
summary: We present a study of a graph parameter in graph theory, named the fractional domatic number. A dominating set in a graph is a set of vertices such that every vertex outside the set is adjacent to a vertex in the set. The domatic number of a graph is ...
Translations: en