Journées de Lancement - Résumés des exposés invités

Jorgen Bang Jensen (Jeudi, 9h30)

Titre : Antistrong digraphs

Résumé : pdf

Nicolas Bousquet (Jeudi, 14h)

Titre : Recoloring sparse graphs

Résumé : Given two (proper) colorings of a graph G, we may ask if it is possible to quickly transform the first into the second in such a way the coloring remains proper at any step of the transformation. We can imagine many ways of defining "transform". During this talk, we will focus on the case where "transforming" a graph means recoloring one vertex at a time.

We will first present several motivations for this problem from the field of operational research to Markov chains. Then we will focus more specifically on a conjecture of Cereceda on the required number of steps to recolor a k-degenerate graph. In particular, we will give some recent partial results about it.

Mohammed Haddad (Vendredi, 9h30)

Titre : Algorithmes auto-stabilisants pour des paramètres de décomposition et de domination dans les graphes

Résumé : Un système distribué est dit auto-stabilisant s’il peut reprendre un comportement correct en un temps fini après l’occurrence de fautes et ce sans intervention extérieure. De ce fait, l’auto-stabilisation est une approche optimiste pour la tolérance aux fautes dans le sens où elle protège le système des fautes transitoires. Un algorithme auto-stabilisant peut être défini selon différents modèles de communication ainsi que différents modèles de calcul. En effet, une preuve de convergence d'un algorithme auto-stabilisant se doit d’être faite selon un démon/scheduler qui peut être centralisé ou distribué, équitable ou non. De plus, la complexité de ces algorithmes peut se calculer selon différentes mesures : moves, steps ou rounds, chacune d'entre elles apportant une connaissance propre sur l'algorithme proposé. Cependant, réussir à borner l'ensemble de ces mesures n'est pas toujours trivial, en particulier pour les cas les plus généraux de démons. La littérature des algorithmes auto-stabilisants est très riche. Cependant, nous allons nous intéresser dans cet exposé aux algorithmes auto-stabilisants pour quelques paramètres de théorie des graphes. En particulier, nous nous focaliserons sur des décompositions et des dominations particulières dans les graphes.

Benjamin Lévêque (Vendredi, 14h)

Titre : Orient to encode

Résumé : Poulalhon and Schaeffer introduced an elegant method to linearly encode a planar triangulation optimally. The method is based on performing a special depth-first search algorithm on a particular orientation of the triangulation: the minimal Schnyder wood. Recent progress toward generalizing Schnyder woods to higher genus enables us to generalize this method to the toroidal case. In the plane, the method leads to a bijection between planar triangulations and some particular trees. For the torus we obtain a similar bijection but with particular unicellular maps (maps with only one face).