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

(Reported to unkwown date) Programming computing media

-- Frédéric Gruau (LRI)

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.

-- George Manoussakis (University of Versailles)

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 ...


Séminaire ouvert

-- Toute l'équipe (LIX, GALAC et IRIF)

Lors d'un séminaire ouvert, le thème n'est pas décidé à l'avance. Tous les membres du séminaires sont invités à participer et peuvent proposer le jour même des interventions plus ou moins longues, des démos ou des questions ouvertes au reste de l'équipe.

Crossing Numbers of K_n for Geometric and Topological Drawings

-- Oswin Aichholzer (TU Graz)

In the area of crossing numbers we ask for minimizing the number of edge intersections in a drawing of a graph. There is a rich variety of crossing number problems: Which graphs do we consider, what exactly is a drawing of a graph and on which surface is it drawn ...

Expérimentations sur les séries génératrices des groupes des tresses

-- Jean Fromentin (Université du Littoral)

Dans cet exposé, je présenterai de nouveaux outils algorithmiques pour étudier les séries génératrices sphériques et géodésiques des groupes des tresses relativement aux générateurs d'Artin ou de Birman-Ko-Lee. Je finirai par une présentation des résultats obtenus et par la formulation de conjectures pour les groupes des tresses à 3 ...

See all

Translations: fr