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.
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 ...
Maximum Independent Set in H-free graphs
Summary: Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1 ...
Attribution Accessit du prix de thèse 2018 Graphes Charles DELORME
Nous avons le plaisir de vous annoncer que l'étudiant George Manoussakis encadré par Johanne Cohen et Antoine Deza a reçu l'accessit du prix de thèse 2018 Graphes Charles DELORME. http://gtgraphes.labri.fr/pmwiki/pmwiki.php/PrixTheseDelorme/PrixTheseDelorme Voici le résumé de sa thèse : Nous introduisons d'abord ...
Translations: en