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
Measuring Similarity between Logical Arguments
Automated Reasoning
Monday 06 March 2023 - 00:00
Salle : 0 - 650
Victor David .............................................

Imputing Out-of-Vocabulary Embeddings with LOVE Ma
Data-Centric Languages and Systems
Monday 20 February 2023 - 00:00
Salle : 455 - PCRI-N
Lihu Chen .............................................

On the Interplay between Software Product Lines an
Automated Reasoning
Tuesday 18 October 2022 - 14:15
Salle : 2013 - DIG-Moulon
Vander Alves .............................................

Combining randomized and observational data: Towar
Automated Reasoning
Thursday 13 October 2022 - 10:30
Salle : 2011 - DIG-Moulon
Bénédicte Colnet .............................................

New Achievements of Artificial Intelligence in Mul
Automated Reasoning
Tuesday 11 October 2022 - 14:15
Salle : 2013 - DIG-Moulon
.............................................