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

The Canadian Traveller Problem on outerplanar graphs

-- Pierre Bergé (LIMOS)

summary: We focus on the PSPACE-complete k-Canadian Traveller Problem, where a weighted graph with a source s and a target t are given. This problem also has a hidden input of cardinality at most k representing blocked edges. The objective is to travel from s to t with the minimum ...


TBA

-- Gervais Mendy Samuel Ouya (Université Cheikh Anta Diop de Dakar, LITA)

summary: TBA

Recent Advances in Distributed Coloring

-- Maxime Flin (Reykjavik University)

summary: The study of distributed graph algorithms aims to understand the limitations inherent to local computations. In a seminal paper, Linial (1992, SIAM J. Computing) introduced the LOCAL model to formalize this question. In this model, the input graph is seen as a communication network where vertices are computers. They ...

An acylic orientation problem with parity constraints

-- Matthieu Petiteau (Université Grenoble Alpes)

summary: Let G = (V, E) be a connected graph and T be a subset of the vertices. An orientation of G is a choice of a direction for each edge of the graph, it is said to be acylic if does not contain any directed cycle. An orientation of G ...

See all

Translations: fr