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.
Fighting epidemics with the maximum spectral subgraph
Summary: Recent developments in mathematical epidemiology have identified a relationship between the time to extinction of an epidemic spreading over a network and the spectral radius of the underlying graph i.e. the largest eigenvalue of its adjacency matrix. At the same time, new generation networking technologies such as NFV ...
Reconfiguration Distribuée de Problèmes de Graphes
Summary: En théorie des graphes, un problème de configuration est le suivant : est-il possible d'aller d'une solution valide d'un problème à une autre, en passant par un chemin de solutions acceptables ? Quelle est la longueur minimale d'un chemin ? Quelle est la complexité ? Par exemple, un problème ...
Some recent results on the integer linear programming formulation for the Max-Cut problem
Summary: Given an undirected graph G=(V,E) where the edges are weighted by an arbitrary cost vector c, a cut S in G associated with a node subset S is the edge subset of E which contains all the edges having exactly one end-node in S. The Maximum Cut ...
Translations: en