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

Compact local certification of MSO properties for several tree-like parameters

-- Hugo Demaret (LISN, Galac)

summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph, in order to certify a certain property about said graph, or the correctness of a data-structure distributed on the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A ...


Complexité du problème de distance d’édition minimum à un line-digraphe

-- Quentin Japhet (LISN, Galac)

summary: La distance d'édition est une mesure classique utilisée pour évaluer la proximité entre un graphe donné et un autre graphe ou une classe de graphes. Cette distance représente le nombre minimum de modifications requises pour transformer le graphe initial en un graphe appartenant à la classe voulue. Une ...

Skipless chain decompositions and improved poset saturation bounds

-- Paul Bastide (LaBRI (Bordeaux))

summary: We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer ...

Asymptotic behaviour of cyclic automata

-- Benjamin Hellouin de Menibus (LISN, Galac)

summary: Cyclic dominance describes models where different states (species, strategies...) are in some cyclic prey-predator relationship: for example, rock-paper-scissors. This occurs in many contexts such as ecological systems, evolutionary games on graphs, etc. Many models exhibit heteroclinic cycles where one state dominates almost the whole space before being replaced by ...

See all

Translations: fr