Français Anglais
Accueil Annuaire Plan du site
Home > Groups > Research groups > Graphs, ALgorithms and Combinatorics (GALaC)
Graphs, ALgorithms and Combinatorics (GALaC)

The GALAC team gathers the researchers from LRI who jointly investigate problems of combinatorics, algorithms, graph theory or networked and distributed systems.

More in depth, the main focus of our research activities is on the following: the combinatorics activity studies the strong interactions and relations that exist between algorithms and algebraic structures. At the same time, graph structures constitute the core of the research of the graph theory activity, which is mainly focused on both structural and algorithmic approach. Efficient algorithms and models for networked systems are designed in the third activity, using theoretical tools like algorithmic game theory and distributed computing.

Group Members
  Group leader
    COHEN Johanne

    CHEN Lin
    COHEN Johanne
    COHEN Nathann
    DELAËT Sylvie
    DEZA Antoine
    DJELLOUL Selma
    FIORENZI Francesca
    FLANDRIN Evelyne
    FORGE David
    HELLOUIN de MENIBUS Benjamin
    HIVERT Florent
    LI Hao
    LOBSTEIN Antoine
    PONS Viviane
    RIMMEL Arpad
    THIÉRY Nicolas
    TOMASIK Joanna
    WEISSER Marc-Antoine

  Non-permanent research staff
    BENASSY Odile
    BERGE Pierre
    BRAY Erik
    FALQUE Justine
    HU Jie
    MORCOS Mira
    PHAM Hong Phong
    RABE Florian
    SHI Hehuan
    TIAN Zengxian

    BERGERON François
    ZHANG Peng
    ZHANG Shurong

    AUGER David
    COUCHENEY Pierre
    DE FEO Luca
    de LAVENERE Vincent
    ELIAS Jocelyne
    FOURNEAU Jean-Michel
    HELIOU Amélie
    PALI Nefton
    RODIER Lise

Research activities
  Graph Theory
  Algorithms for networked systems

Contracts & grants
  Attractivité 2018 B

Software & patents
  Cartaj: Classification Of RNA threeway Junctions
  Sage-Combinat: To improve the open source mathematical system Sage
  SageMath: A free open-source mathematics software system
  aSHIIP: A random topology generator of interdomain
  GARN: Game Algorithms for RNa 3D sampling

Recent Ph.D. dissertations & faculty habilitations
  Representation of monoids and lattice structures in the combinatorics of Weyl groups
  Hypercubes latins maximin pour l’échantillonnage de systèmes complexes
  Conception et analyse de protocoles, pour les réseaux de capteurs sans fil, prenant en compte la consommation d'énergie

Some recent results on the integer linear programming formulation for the Max-Cut problem
Hung Nguyen
30 November 2018 00h00

Maximum Independent Set in H-free graphs
Edouard BONNET
5 October 2018 14h30

Binary pattern of length greater than 14 are abelian-2-avoidable
Matthieu Rosenfeld
29 June 2018 14h30

Caractérisation de réseaux égocentrés par l'énumération de leurs sous-graphes induits
Raphaël Charbey
15 June 2018 14h30

Mariage stable auto-stabilisant et distribué
Marie Laveau
13 April 2018 14h30

A Two-level Auction for Resource Allocation in Multi-tenant C-RAN
Mira Morcos
9 March 2018 14h30

A concurrent lock-free algorithm for computing a finite semigroup
James Mitchell
12 January 2018 14h30

Computing the growth rate of the number of patterns in a tiling
Benjamin Hellouin
22 December 2017 14h30

Cycles dans les produits cartésiens de graphes
Evelyne Flandrin
1 December 2017 14h30

Evelyne Flandrin
28 April 2017 14h30

Lattice polytopes with large diameter and many vertices
Antoine Deza
31 March 2017 14h30

Euler Polytopes and Convex Matroid Optimization
George Manoussakis
25 March 2016 14h30

Multi-armed bandit for distributed inter-cell interference coordination.
Johanne Cohen
29 January 2016 14h30

Locating pairs of vertices on Hamiltonian cycles
Hao Li
22 January 2016 14h30

Approximate Consensus in Highly Dynamic Networks
Bernadette Charron-Bost
10 April 2015 10h00

Marches aléatoires dans les réseaux dynamiques : auto-stabilisation et mécanismes probabiliste
Devan Sohier,
27 March 2015 14h30

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
Hirotaka Ono
13 February 2015 14h30

Solving Matching Problems Efficiently in Bipartite Graphs
Selma Djelloul
31 January 2015 14h30

Self-stabilizing local k-placement of replicas with minimal variance.
Volker Turau
8 December 2014 15h30

2-distance coloring of not-so-sparse graphs.
Clement Charpentier
16 May 2014 14h30

Sur la structure palindromique des mots
Srecko Brlek
9 May 2014 14h30

Distributed Selfish Algorithms for Max-Cut game.
Lise Rodier
11 April 2014 10h30

Cycles in line graphs and the preimage graphs
Kiyoshi Yoshimoto
28 March 2014 14h30

Intervals of the Tamari lattice.
Viviane Pons
28 March 2014 10h30

Combinatoire et algorithmique dans les classes de permutations à motifs exclus.
Adeline Pierrot
14 March 2014 10h30

On Kinetic Delaunay Triangulations
Natan Rubin
7 February 2014 11h00

Finding an odd hole through two vertices of a planar graph in polynomial time
Marcin Kamiński
7 February 2014 10h00

Résultats majeurs
Software & patents