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

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

Activités de recherche : Graph Theory

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
Forum dev-LRI
Tuesday 26 November 2019 - 14:00
Salle : 445 - PCRI-N
Jonas et Erik .............................................

Langage d'icônes et visualisation d'ensembles : mé
Thursday 14 November 2019 - 14:30
Salle : 475 - PCRI-N
Jean-Baptiste Lamy .............................................

Algorithms for Cell Reprogramming Strategies in Bo
Thursday 07 November 2019 - 00:00
Salle : 475 - PCRI-N
Hugues Mandon .............................................

On the weakest failure detector for atomic multica
Distributed algorithms
Tuesday 05 November 2019 - 10:30
Salle : 465 - PCRI-N
Pierre Sutra .............................................

Matchings and related structures with Specified Co
Graph Theory
Thursday 17 October 2019 - 14:30
Salle : 445 - PCRI-N
Yannis Manoussakis .............................................