GALaC team at LRI, Paris-Sud
GALaC is a research group at LRI, Paris-Sud University. We are focused on graph theory, combinatorics and network distributed systems algorithmic.
A global presentation of research activities in GALaC was made in 2013 for the AERES evaluation: Slides AERES 2013 and projet.
Recent Posts
Problème du domino pour les homshifts généralisés (ou H-coloration de graphes de Cayley)
summary: On s’intéresse à certains pavages du plan : des colorations de la grille Z² par un nombre fini de couleurs, et respectant un certain nombre de contraintes. Le problème du domino est le suivant : étant donné un nombre fini de motifs interdits, est-ce qu’il est possible de colorier ...
TBA
summary: TBA
Mobile Agents in Adversarial Networks: Perpetual Exploration in Presence of Malicious Host
summary: Perpetual exploration is a central problem in distributed computing, requiring a team of mobile agents to repeatedly visit every node of a network indefinitely. While the problem is well understood in benign environments, its complexity increases dramatically in the presence of adversarial nodes. A particularly challenging scenario arises even ...
Treillis de framing et coordonnées cubiques
summary: Les treillis de framing sont des familles d'ordres partiels définies très récemment par [von Bell--Ceballos, 2025] et [Berggren--Serhiyenko, 2024], en lien avec les polytopes de flots. On y retrouve comme cas particuliers notables l'ordre faible sur le groupe symétrique, le treillis de Tamari, le treillis booléen et ...
Compléter des colorations partielles de hom shifts
summary: On étudie les shifts ou espaces de pavages de type fini : des colorations de la grille régulière infinie qui évitent un ensemble fini de motifs interdits. Il s'agit d'un modèle étudié en particulier comme source apparemment infinie de problèmes indécidables.
Les hom shifts sont une restriction du ...
Translations: fr