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.

(Reported to unkwown date) The Bron-Kerbosch algorithm with vertex ordering is output sensitive.

-- George Manoussakis (University of Versailles)

summary: The Bron-Kerbosch algorithm is a well known maximal clique enumeration algorithm. So far it was unknown whether it was output sensitive or not. In this paper we partially answer this question by proving that the Bron-Kerbosch Algorithm with vertex ordering, first introduced and studied by Eppstein, Löffler and Strash ...


L-orientations of graphs

-- Kenta Ozeki (Yokohama National University)

summary: An orientation of an (undirected) graph G is an assignment of directions to each edge of G. In this talk, we consider an orientation such that the out-degree of each vertex is contained in a given list. We introduce several relations to graph theory topics and pose our main ...

PHD defense: A guide book for the traveller on graphs full of blockages

-- Pierre Bergé (LRI, University of Paris Saclay)

summary: We study NP-hard problems dealing with graphs containing blockages.

We analyze cut problems via the parameterized complexity framework. The size p of the cut is the parameter. Given a set of sources {s_1,...,s_k} and a target t, we propose an algorithm deciding whether a cut of size at ...

Overcoming interference in the beeping communication model

-- Fabien Dufoulon (University Paris South)

summary: Small inexpensive inter-communicating electronic devices have become widely available. Although the individual device has severely limited capabilities (e.g., basic communication, constant-size memory or limited mobility), multitudes of such weak devices communicating together are able to form low-cost, easily deployable, yet highly performant networks. Such distributed systems present significant ...

See all

Translations: en