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
Dipayan Chakraborty, Florent Foucaud, Anni Hakanen, Michael Henning, Annegret Wagler - 1 décembre 2024
Progress towards the two-thirds conjecture on locating-total dominating sets
Discrete Mathematics
Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Michaela Seifrtová - 1 décembre 2024
Computational complexity of covering disconnected multigraphs
Discrete Applied Mathematics
Lhouari Nourine, Jean-Marc Petit, Simon Vilmin - 1 décembre 2024
Towards declarative comparabilities: Application to functional dependencies
Journal of Computer and System Sciences
Antoine Dailly, Harmender Gahlawat, Zin Mar Myint - 23 septembre 2024
The Closed Geodetic Game: algorithms and strategies
Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing - 26 août 2024
Algorithms and Complexity for Path Covers of Temporal DAGs
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Mohammed Elaroussi, Lhouari Nourine, Simon Vilmin - 26 août 2024
Half-space separation in monophonic convexity
Mathematical Foundation of Computer Science (MFCS)
Ocyna Rudmann, Anatolia Batruch, Emilio Paolo Visintin, Nicolas Sommet, Pascal Bressoux, Céline Darnon, Marinette Bouet, Marco Bressan, Genavee Brown, Carlos Cepeda, Anthony Cherbonnier, Marie Demolliens, Anne-Laure de Place, Olivier Desrichard, Théo Ducros, Luc Goron, Brivael Hemon, Pascal Huguet, Eric Jamet, Ruben Martinez, Vincent Mazenod, Nathalie Mella, Estelle Michinov, Nicolas Michinov, Nana Ofosu, Pascal Pansu, Laurine Peter, Benoit Petitcollot, Celine Poletti, Isabelle Régner, Mathilde Riant, Anais Robert, Camille Sanrey, Arnaud Stanczak, Farouk Toumani, Simon Vilmin, Eva Vives, Fabrizio Butera - 1 août 2024
Cooperative learning reduces the gender gap in perceived social competences: A large-scale nationwide longitudinal experiment.
Journal of Educational Psychology
Ocyna Rudmann, Anatolia Batruch, Emilio Paolo Visintin, Nicolas Sommet, Pascal Bressoux, Céline Darnon, Marinette Bouet, Marco Bressan, Genavee Brown, Carlos Cepeda, Anthony Cherbonnier, Marie Demolliens, Anne-Laure de Place, Olivier Desrichard, Théo Ducros, Luc Goron, Brivael Hemon, Pascal Huguet, Eric Jamet, Ruben Martinez, Vincent Mazenod, Nathalie Mella, Estelle Michinov, Nicolas Michinov, Nana Ofosu, Pascal Pansu, Laurine Peter, Benoit Petitcollot, Celine Poletti, Isabelle Régner, Mathilde Riant, Anais Robert, Camille Sanrey, Arnaud Stanczak, Farouk Toumani, Simon Vilmin, Eva Vives, Fabrizio Butera - 1 août 2024
Cooperative learning reduces the gender gap in perceived social competences: A large-scale nationwide longitudinal experiment.
Journal of Educational Psychology
Dipayan Chakraborty, Florent Foucaud, Aline Parreau, Annegret K Wagler - 22 juillet 2024
On three domination-based identification problems in block graphs
Fundamenta Informaticae
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios Thilikos, Alexandre Vigny - 8 juillet 2024
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
LICS 2024 - 39th ACM/IEEE Symposium on Logic in Computer Science
Progress towards the two-thirds conjecture on locating-total dominating sets
Discrete Mathematics
Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Michaela Seifrtová - 1 décembre 2024
Computational complexity of covering disconnected multigraphs
Discrete Applied Mathematics
Lhouari Nourine, Jean-Marc Petit, Simon Vilmin - 1 décembre 2024
Towards declarative comparabilities: Application to functional dependencies
Journal of Computer and System Sciences
Antoine Dailly, Harmender Gahlawat, Zin Mar Myint - 23 septembre 2024
The Closed Geodetic Game: algorithms and strategies
Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing - 26 août 2024
Algorithms and Complexity for Path Covers of Temporal DAGs
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Mohammed Elaroussi, Lhouari Nourine, Simon Vilmin - 26 août 2024
Half-space separation in monophonic convexity
Mathematical Foundation of Computer Science (MFCS)
Ocyna Rudmann, Anatolia Batruch, Emilio Paolo Visintin, Nicolas Sommet, Pascal Bressoux, Céline Darnon, Marinette Bouet, Marco Bressan, Genavee Brown, Carlos Cepeda, Anthony Cherbonnier, Marie Demolliens, Anne-Laure de Place, Olivier Desrichard, Théo Ducros, Luc Goron, Brivael Hemon, Pascal Huguet, Eric Jamet, Ruben Martinez, Vincent Mazenod, Nathalie Mella, Estelle Michinov, Nicolas Michinov, Nana Ofosu, Pascal Pansu, Laurine Peter, Benoit Petitcollot, Celine Poletti, Isabelle Régner, Mathilde Riant, Anais Robert, Camille Sanrey, Arnaud Stanczak, Farouk Toumani, Simon Vilmin, Eva Vives, Fabrizio Butera - 1 août 2024
Cooperative learning reduces the gender gap in perceived social competences: A large-scale nationwide longitudinal experiment.
Journal of Educational Psychology
Ocyna Rudmann, Anatolia Batruch, Emilio Paolo Visintin, Nicolas Sommet, Pascal Bressoux, Céline Darnon, Marinette Bouet, Marco Bressan, Genavee Brown, Carlos Cepeda, Anthony Cherbonnier, Marie Demolliens, Anne-Laure de Place, Olivier Desrichard, Théo Ducros, Luc Goron, Brivael Hemon, Pascal Huguet, Eric Jamet, Ruben Martinez, Vincent Mazenod, Nathalie Mella, Estelle Michinov, Nicolas Michinov, Nana Ofosu, Pascal Pansu, Laurine Peter, Benoit Petitcollot, Celine Poletti, Isabelle Régner, Mathilde Riant, Anais Robert, Camille Sanrey, Arnaud Stanczak, Farouk Toumani, Simon Vilmin, Eva Vives, Fabrizio Butera - 1 août 2024
Cooperative learning reduces the gender gap in perceived social competences: A large-scale nationwide longitudinal experiment.
Journal of Educational Psychology
Dipayan Chakraborty, Florent Foucaud, Aline Parreau, Annegret K Wagler - 22 juillet 2024
On three domination-based identification problems in block graphs
Fundamenta Informaticae
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios Thilikos, Alexandre Vigny - 8 juillet 2024
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
LICS 2024 - 39th ACM/IEEE Symposium on Logic in Computer Science
Toutes les publis se trouvent ici