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
Heterogeneous Treatment Effects Estimation: When M
Raisonnement automatique
Thursday 02 June 2022 - 10h30
Salle : 2011 - DIG-Moulon
Naoufal Acharki .............................................

Witness Generation for JSON Schema
Langages et systèmes centrés données
Monday 30 May 2022 - 00h00
Salle : 455 - PCRI-N
Mohamed-Amine BAAZIZI .............................................

TUTORIAL CODALAB - Apprenez à organiser un challen
Wednesday 13 April 2022 - 00h00
Salle : 1 - DIG-Moulon
Adrien Pavao .............................................

Generative Neural Networks for Observational Causa
Raisonnement automatique
Thursday 07 April 2022 - 10h30
Salle : 2011 - DIG-Moulon
Diviyan Kalainathan .............................................

Datamining in Epi- and Phylogenetics
Tuesday 15 March 2022 - 11h00
Salle : 455 - PCRI-N
Thomas Haschka .............................................