Partenaires


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Structuration Scientifique > Informatique > Combinatoire > Projet thématique « Algorithmes de graphes »

Projet thématique « Algorithmes de graphes »

Le projet vise à obtenir des avancées pour plusieurs problèmes liés à la structure ou à la coloration de graphes.

Concernant les cheminements dans les graphes, nous allons poursuivre l’étude des cheminements à distance d que nous avons introduit récemment (graphes généraux et grilles 2D et nD), et mettre au jour des liens avec d’autres paramètres comme les radio-colorations. Concernant les colorations de graphes, nous souhaitons continuer l’exploration des colorations avec contraintes de distance, en particulier, par l’étude du « packing coloring » qui est un paramètre introduit récemment par Godard et al.. Notre objectif est de trouver des algorithmes performants pour de nouvelles classes de graphes (en particuliers les graphes de distances) et d’identifier des liens avec d’autres paramètres de coloration. Nous souhaitons également étudier l’ajout de contraintes de type « radio » au packing coloring. Des variantes de ces paramètres seront considérées (par listes, fractionnaire, circulaire, …).

D’autre part, nous souhaitons étudier des problèmes de définition de sous-graphes contraints d’un graphe, inspirés des problèmes de dimensionnement rencontrés dans le monde des réseaux. L’objectif est de proposer des algorithmes efficaces pour le calcul de sous-graphes répondant à des contraintes de degré et de connectivité , et ce sur des instances de taille significative. Enfin nous souhaitons étudier des problèmes d’affectation de dates aux nœuds d’une collection de sous-chemins d’un graphe. Cette problématique est directement inspirée des contraintes de communication rencontrée dans les réseaux sans-fil. Notre objectif est de déterminer la complexité de ce problème dans différentes classes de graphes et de proposer des algorithmes avec garantie de performance pour les classes difficiles.

Chercheurs et enseignants-chercheurs permanents :


LE2I - Laboratoire Electronique, Informatique et Image | webmestre : Antoine Trapet | info légales | logo SPIP 2