Thème Algorithmique, Graphes, Complexité

Présentation

Les thèmes abordés par Algorithmes, Graphes et Complexité sont principalement : (1) des propriétés structurelles sur les graphes/treillis et leurs conséquences algorithmiques, et (2) l'algorithmique géométrique avec un intérêt particulier sur la géométrie discrète.
 
Il est commun dans l'étude d'objets combinatoires d'appliquer la technique du "Diviser pour Mieux régner" de Descartes, ie, définir des opérations sur les objets et ensuite décomposer à l'aide des opérations pour tenter d'expliquer la complexité des objets étudiés. Le groupe a une expertise dans les décompositions des graphes et des treillis, et leurs applications algorithmiques. Des exemples de décompositions étudiées sont par exemple la décomposition arborescente et la largeur de rang dont le but est d'étudier les classes de graphes qui ressemblent à des arbres,  mais aussi des décompositions basées sur des séparateurs comme les cliques ou stables ou skew-partition avec des applications en coloration de graphes. Les décompositions de treillis étudiés peuvent être des constructions récursives basées sur la copie d'ensembles convexes ou de posets colorés. Voici quelques applications algorithmiques des décompositions étudiées :
 
   - Les algorithmes d'énumération dans les (hyper)graphes et treillis. Le groupe est reconnu dans les problèmes d'énumération de sous-ensembles de sommets satisfaisant une certaine propriété. On peut citer par exemple l'équivalence entre l'énumération des dominants minimaux et le célébre problème des transversaux minimaux.
 
  - La représentation de treillis. Cette question est abordée dans le cadre de la Dualisation des treillis, une généralisation du problème des transversaux minimaux.
 
  - Problèmes d'optimisation. Des exemples de problèmes d'optimisation étudiés sont la coloration de graphes, des problèmes de domination, différentes formes d'homorphisme de graphes. Le groupe s'intéresse aussi bien à l'obtention de bornes inf/sup sur des paramètres comme le nombre chromatique ou des codes identifiants, mais aussi des bornes inf/sup sur la complexité paramétrée de ces problèmes.
 
  - Problèmes de packing et de covering, e.g., Erdös-Posa.
 
Les principaux thèmes en algorithmique géométrique sont d'ordre calculatoire en géométrie discréte comme par exemple le calcul  d'enveloppes convexes dans les espaces euclidiens. Les membres sont experts dans la conception d'algorithmes compétitifs pour  calculer/approcher les enveloppes convexes de plusieurs configurations dans le plan euclidien (problèmes souvent NP-hard).  Des membres du groupe participent régulièrement au challenge CG:SHOP, organisé durant la conférence internationale SoCG; ils ont d'ailleurs gagné le challenge en 2021, qui portait sur le problème du coordinated robot motion planning.
 
Mots-clé: graphes; mesures de complexité de graphes; décompositions de graphes; théorie algorithmique des treillis; géométrie algorithmique; convexité discréte; algorithmes d’énumération.

Dernières Publications

Osama Allabwani, Olivier Blazy, Pascal Lafourcade, Charles Olivier-Anclin, Olivier Raynaud - 1 juin 2026
Sanitizable Signatures with Different Admissibility Policies for Multiple Sanitizers
ACM Asia Conference on Computer and Communications Security (ASIA CCS '26)

Kyle Burke, Antoine Dailly, Nacim Oijid - 4 mars 2026
Complexity and Algorithms for Arc-Kayles and Non-disconnecting Arc-Kayles
The 20th International Conference and Workshops on Algorithms and Computation (WALCOM 2026)

Florent Foucaud, Paras Vinubhai Maniya, Kaustav Paul, Dinabandhu Pradhan - 1 mars 2026
Locating-dominating partitions for some classes of graphs
Discrete Mathematics

Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté, Florent Madelaine - 23 février 2026
Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide
CSL 2026

Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale - 12 février 2026
Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
12th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2026)

Aude Marêché, Isabelle Debled-Rennesson, Fabien Feschet, Phuc Ngo - 6 février 2026
Local Fan of Digital Planes for Parameter-Free Normal Vector Estimation on Digital Surfaces


Dipayan Chakraborty, Florent Foucaud, Michael Henning, Tuomo Lehtilä - 1 février 2026
Identifying codes in graphs of given maximum degree: Characterizing trees
Discrete Mathematics

Pierre Bergé, Antoine Dailly, Yan Gerard - 20 janvier 2026
Nemesis, an Escape Game in Graphs


Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté - 7 janvier 2026
Transducing Linear Decompositions of Tournaments


Antoine Dailly, Florent Foucaud, Anni Hakanen - 1 janvier 2026
Algorithms and hardness for Metric Dimension on digraphs
Journal of Computer and System Sciences

Toutes les publis se trouvent ici

Projets

Argtowin

ALGOPT-GI

CHAIRE PROF JUNIOR

ALGOMETRIC - Algorithmique de problèmes métriques pour les réseaux de transport

GRALMECO - Algorithmique des problèmes de couverture métriques dans les graphes

Tous les projets se trouvent ici

Equipe

Responsables

Enseignants-Chercheurs

Post-docs

Doctorants