Theme Algorithmics, Graphs, Complexity


The AGC team focuses on algorithmic in graphs, lattices and geometry. It involves studying structural  properties  in order to design efficient algorithms. The main orientations are:
  1. Enumeration of combinatorial objects in graphs and efficient algorithms for optimization or counting problems.
  2. Representations of lattices and efficient algorithms for lattices.
  3. Structures and decompositions of graphs.
  4. Algorithmic of objects from geometry.
The team is also interested in applications in data mining and data quality.

Last publications

Lhouari Nourine, Simon Vilmin - June 1, 2020
Hierarchical decompositions of dihypergraphs

Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwénaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, Jean-Sébastien Sereni - March 20, 2020
Revisiting a theorem by Folkman on graph colouring
The Electronic Journal of Combinatorics

Kaoutar Ghazi, Sébastien Marchal, Andon Tchechmedjiev, Pierre-Antoine Jean, Nicolas Sutton-Charani, Sébastien Harispe - Jan. 28, 2020
Classification de phrases courtes : des approches non-supervisées aux approches faiblement supervisées
EGC 2020 - Extraction et Gestion des Connaissances (TextMine - Atelier sur la fouille de textes)

Marthe Bonamy, Oscar Defrain, Meike Hatzel, Jocelyn Thiebaut - Jan. 17, 2020
Avoidable paths in graphs

Rahul Arya, Sunil Arya, Guilherme da Fonseca, David Mount - Jan. 5, 2020
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
SODA 2020

Benjamin Bergougnoux, Mamadou Moustapha Kanté - Dec. 5, 2019
A Meta-Algorithm for Solving Connectivity and Acyclicity Constraints on Locally Checkable Properties Parameterized by Graph Width Measures

Oscar Defrain, Lhouari Nourine - Nov. 29, 2019
Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7-Free and P_8-Free Chordal Graphs

Antoine Dailly, Florent Foucaud, Adriana Hansberg - Nov. 1, 2019
Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
Discrete Mathematics

Farah Dernaika, Nora Cuppens-Boulahia, Frédéric Cuppens, Olivier Raynaud - Aug. 26, 2019
Semantic Mediation for A Posteriori Log Analysis
ARES ’19

Alessio Conte, Roberto Grossi, Mamadou Kanté, Andrea Marino, Takeaki Uno, Kunihiro Wasa - Aug. 26, 2019
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs
MFCS 2019 - 44th International Symposium on Mathematical Foundations of Computer Science

All publications are here