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
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
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
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 ...
Translations: fr