Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Reconfiguration Distribuée de Problèmes de Graphes
Mikael Rabie

08 February 2019, 14h30
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche : Théorie des graphes

Résumé :
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 de recoloration est de savoir si on peut aller d'une coloration à une autre, en changeant à chaque étape intermédiaire la couleur d'un sommet tout en gardant une coloration valide.
Dans cet exposé, nous allons considérer de manière distribuée deux problèmes de reconfiguration (recoloration, et reconfiguration d'ensembles maximaux indépendants). Au lieu de faire une modification ponctuelle à chaque étape, on va chercher à paralléliser les étapes (par exemple, en recolorant un ensemble indépendant de sommets à chaque étape). Le but devient alors, dans le modèle LOCAL, de savoir combien de communications est nécessaire pour que chaque sommet produise un planning de reconfiguration (après k communications, un sommet connaît son voisinage à distance k).
Dans le cas de la recoloration, on prouve que l'ajout de couleurs supplémentaires est nécessaire pour que certaines solutions existent. On analysera en particulier le cas d'arbres et de grilles toroïdales dans lesquelles on a deux 3-colorations et où on s'autorise une couleur supplémentaire. Dans le cas des arbres, il est possible de trouver un planning de longueur constante après log n communications. Dans le cas des grilles, un nombre de communications linéaire est nécessaire.
Dans le cas d'ensembles indépendants maximaux, on expliquera d'abord les différentes étapes possibles, pour justifier celle utilisée : a chaque étape, l'ensemble indépendant intermédiaire doit couvrir à distance 4 chaque sommet. Avec ces contraintes, un planning constant peut être trouvé après log* n communications, et un planning linéaire peut être trouvé après un nombre constant de communications.
Ces travaux ont été faits en collaboration avec Marthe Bonamy, Keren Censor-Hillel, Paul Ouvrard, Jara Uitto et Jukka Suomela

Pour en savoir plus :
Séminaires
Langage d'icônes et visualisation d'ensembles : mé
Thursday 24 October 2019 - 14h30
Salle : 475 - PCRI-N
Jean-Baptiste Lamy .............................................

Matchings and related structures with Specified Co
Théorie des graphes
Thursday 17 October 2019 - 14h30
Salle : 445 - PCRI-N
Yannis Manoussakis .............................................

Conservation of structural long-range modules in R
Thursday 17 October 2019 - 14h30
Salle : 475 - PCRI-N
Vladimir Reinharz .............................................

Overcoming interference in the beeping communicati
Algorithmique distribuée
Friday 11 October 2019 - 14h30
Salle : 445 - PCRI-N
Fabien Dufoulon .............................................

Local checkability: a notion that started in the c
Algorithmique distribuée
Tuesday 08 October 2019 - 11h00
Salle : 465 - PCRI-N
Prof. Kutten Shay .............................................