Thème Algorithmique, Graphes, Complexité

Présentation

Le thème AGC est centré sur l’algorithmique des graphes, des treillis et de géométrie. Il s’agit d’étudier les propriétés des structures combinatoires afin de concevoir des algorithmes efficaces. Les principales orientations sont :

  1. Enumération d’objets combinatoires dans les graphes et algorithmes efficaces pour des problémes d’optimisation ou de comptage.
  2. Représentations des treillis et algorithmes efficaces pour passer d’une représentation à une autre.
  3. Structures et décompositions de graphes.
  4. Algorithmique des objets issus de la géométrie.

Le thème s'intéresse aussi aux applications dans la fouille de données et qualité de données.

Dernières Publications

Florent Foucaud, Benjamin Gras, Anthony Perez, Florian Sikora - 1 septembre 2021
On the Complexity of Broadcast Domination and Multipacking in Digraphs
Algorithmica

Florent Foucaud, Hervé Hocquard, Dimitri Lajou - 1 septembre 2021
Complexity and algorithms for injective edge-coloring in graphs
Information Processing Letters

Mohammed Elaroussi, Lhouari Nourine, Mohammed Radjef - 29 mars 2021
Lattice point of view for argumentation framework


Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos - 7 septembre 2020
A linear fixed parameter tractable algorithm for connected pathwidth
28th Annual European Symposium on Algorithms (ESA)

Oscar Defrain - 2 septembre 2020
On the dualization problem in graphs, hypergraphs, and lattices


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


Oscar Defrain, Lhouari Nourine - 1 avril 2020
Dualization in lattices given by implicational bases
Theoretical Computer Science

Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwénaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, Jean-Sébastien Sereni - 20 mars 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 - 28 janvier 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 - 17 janvier 2020
Avoidable paths in graphs


Toutes les publis se trouvent ici

Projets