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
Knowledge Graph Refinement based on Triplet BERT-N
Gestion de données du Web
Monday 29 November 2021 - 13h00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Raisonnement automatique
Monday 15 November 2021 - 13h00
Salle : 445 - PCRI-N
Hui Yang .............................................

Semantic approaches to predict the presence of asb
Intégration de données et de connaissances
Monday 08 November 2021 - 13h00
Salle : 455 - PCRI-N
Thamer Mecharnia .............................................

Pierre Andrieu - Agrégation de classements pour le
Thursday 21 October 2021 - 00h00
Salle : 435 - PCRI-N
.............................................

A counting argument for graph colouring
Théorie des graphes
Friday 08 October 2021 - 11h00
Salle : 445 - PCRI-N
Francois Pirot .............................................