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
Enumération des cartes planaires à trois bords par découpage en tranches
Parmi toutes les techniques d’énumération des cartes planaires (graphes plongés sur la sphère à deux dimensions), une des approches conceptuellement les plus simples et directes consiste à découper la carte en tranches: si on dispose d’une règle canonique de découpage et que les tranches ainsi obtenues sont faciles ...
(Reported to unkwown date) Programming computing media
summary: We consider computing media consisting of billions of small identical Processing Elements (PE) communicating locally in space, and with an homogeneous and isotropic distribution. Computing media can scale arbitrary in size. Thus, they represent parallel architectures whose power can grow without limit. However, programming computing media is difficult.
In ...
(Reported to unkwown date) The Bron-Kerbosch algorithm with vertex ordering is output sensitive.
summary: The Bron-Kerbosch algorithm is a well known maximal clique enumeration algorithm. So far it was unknown whether it was output sensitive or not. In this paper we partially answer this question by proving that the Bron-Kerbosch Algorithm with vertex ordering, first introduced and studied by Eppstein, Löffler and Strash ...
Self-Stabilization and Byzantine Tolerance for Maximal Independent Set
summary: We analyze the impact of transient and Byzantine faults on the construction of a maximal independent set in a general network. We adapt the self-stabilizing algorithm presented by Turau for computing such a vertex set. Our algorithm is self-stabilizing, and also works under the more difficult context of arbitrary ...
A counting argument for graph colouring
summary: In 2010, Moser and Tardos introduced an algorithmic version of the celebrated Lovász Local Lemma using the entropy compression method. Their method is now widely used in the community and has become a standard of the probabilistic method, mainly because it often provides the tightest existential bounds. However, it ...
Modèles de dimères sur graphes minimaux : au-delà du cas elliptique
Les modèles de dimères sur les graphes planaires ont fait leur début en tant qu'objet d'étude mathématique avec les travaux de Kasteleyn dans les années 1960. Au début des années 2000, d'importants résultats théoriques sont démontrés, dont deux résultats dans des directions différentes : - la construction du diagramme ...
Translations: fr