GALAC

Graphes, ALgorithmes et Combinatoire (GALaC)

L'équipe GALAC rassemble les chercheurs du LISN qui travaillent sur des thématiques de combinatoire, d'algorithmique, de théorie des graphes, de systèmes en réseaux et distribués. Plus précisément, nos domaines de recherche sont les suivants : notre recherche en combinatoire porte sur les fortes interactions et relations existant entre les algorithmes et les structures algébriques, et la recherche en théorie des graphes sur des propriétés structurelles et des problèmes de décomposition. Des algorithmes et modèles efficaces pour les systèmes en réseaux sont développés dans la troisième activité de l'équipe, en utilisant le formalisme de la théorie des jeux et du calcul distribué.

Thèmes de recherche

L’équipe GALaC a trois principaux thèmes de recherche.

Le but principal de ce groupe est de concevoir, modéliser, étudier le controle et les performances des algorithmiques conçus spéficiquement pour les systèmes répartis et leurs applications. La contribution scientifique que nous visons est à la fois théorique avec le développement de nouveaux modèles mathématiques et des preuves de qualité et mais aussi bien appliquée avec le développement d’outils innovants pour différents types de réseaux (opportunistes, centrés sur le contenu ou congitifs).

Plus précisément les objectifs du group ANS (pour Algorithms for Networked systems) sont :

  • D’établir des briques de bases pour la conception et l’optimisation des systèmes en réseaux. Ceci inclue la théorie du controle, la théorie des jeux, les algorithmes répartis et particulièrement l’auto-stabilisation et plus généralement la tolérance aux fautes aussi bien que la simulation de systèmes via des modèles à évenements discrets.
  • De concevoir des algorithmes efficaces et des protocoles basés sur le développement des trames théoriques, d’en evaluer les performance grace à des scénarii pratiques. Ceci inclue les réseaux sans fils opportunistes (entre autre réseaux de robots, réseau sans fils ad hoc, réseaux de capteurs), les futures infrasctrutures et protocoles pour l’internet (information, Réseau centrés sur le contenus), la sécurité et la sureté dans les systemèmes cyber-physiques.

Les collaborations de cet axe prennent place sur les 5 continents.

L’intérêt principal de cette activité est l’étude des relations entre les structures algébriques et les algorithmes. Les chercheurs s’attachent particulirement aux sujets suivants:

  • les structures algébriques (combinatoire des algèbres de Hopf, Opérades, Monoides, …) relatives aux algorithmes;
  • la combinatoire énumérative et la dynamique symbolique.
  • Les logiciels orientés objets conçus pour la modélisation des mathématiques, en particulier le développement du logiciel SageMath;

Plus précisément, les projets de recherches relèvent de la combinatoire algébrique, sont à l’interface de la combinatoire énumérative et concernent l’analyse d’algorithmes d’un point de vue des calculs symboliques et algébriques ou de calcul algébriques. Les objectifs sont doubles: d’abord, grâce à une généralisation massive de la notion de série génératrice nous espérons proposer un canevas théorique permettant l’étude du comportement fin de nombreux et différents algorithmes et ensuite et de manière réciproque l’étude des même algorithmes ouvre de nouvelles pistes pour la découverte d’objets ou d’identités algébriques d’intérêt. Ces identités ont plusieurs applications en mathématiques, en particulier dans la théorie des représentations mais aussi en physique (principalement en physique statistique).

Les recherches reposent largement sur l’expérimentation par ordinateur, il s’en suit une part importante de développement via le projet logiciel Sage-Combinat.

Cependant, le niveau de sophistication, la souplesse et la qualité des outils de calcul requis atteint un point où à grande échelle le développement collaboratif est essentiel. La conception et le développement collaboratif d’un tel logiciel soulève la recherche de qualité. Les défis sont tant du domaine de l’informatique qu’autour de la modélisation mathématique et de la gestion d’un grande hiérarchie de (orientée objet) classes, etc.

Ces questions spécifiques posent aussi de manière plus générale des questions combinatoires. Il est alors envisager un travail sur la combinatoire enumérative, les automates cellulaires en particulier les arbres.

Cet axe nourrit des collaborations régulières en France mais aussi avec l’Allemagne, l’Amérique du nord et l’Inde.

Le sujet principal est une point de vue structurel et algorithmique. L’équipe a établi une expertise comprenant les problèmes tel que trouver les grands cycles d’un graphe donné, colorier un graphe, résoudre des problèmes de couverture, ou faire avancer la théorie des graphes en trouvant les graphes extrèmes répondant à une contrainte.

La généralisation de quelques problèmes est aussi considérée pour les graphes arêtes ou sommets colorés. Par exemple, il a été étudié les graphes couvrants colorés pour des graphes arêtes ou sommets colorés. De manière alternative il a été recherche l’ensemble dominant dans un graphe ayant au moins un sommet de chaque couleur. au delà de l’intérêt purement théoriques ces démarches ont un grand intérêt aussi bien dans le domaine de la bioinformatique que dans celui du Web.

Bon nombre des questions que nous considérons peuvent aussi être déclarée en termes d’optimisation de linéaire. Ce qui ouvre des perspectives.

Nous avons de nombreuses collaborations avec les groupes français : LaBRILaboratoire Bordelais de Recherche en Informatique, LIRMMLaboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, LIAFALaboratoire d'Informatique Algorithmique: Fondements et Applications et LIMOSLaboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes aussi bien qu’en Europe, en Amérique du nord et du sud et principalement en Asie avec la Chine, le Japan, l’Inde.

Coordination

L’équipe

Publications récentes

  • Thèse

    Qiancheng Ouyang. Some colouring problems in edge/vertex-coloured graphs : Structural and extremal studies. Combinatorics [math.CO]. Université Paris-Saclay, 2023. English. ⟨NNT : 2023UPASG060⟩. ⟨tel-04505756⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Thèse

    Noémie Cartier. Lattice properties of acyclic pipe dreams. Combinatorics [math.CO]. Université Paris-Saclay, 2023. English. ⟨NNT : 2023UPASG065⟩. ⟨tel-04496040⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Marc Velay, Bich-Liên Doan, Arpad Rimmel, Fabrice Popineau, Fabrice Daniel. Benchmarking Robustness of Deep Reinforcement Learning approaches to Online Portfolio Management. 2023 International Conference on Innovations in Intelligent Systems and Applications (INISTA), Sep 2023, Hammamet, Tunisia. pp.1-6, ⟨10.1109/INISTA59065.2023.10310402⟩. ⟨hal-04473989⟩

    AO, GALaC, LaHDAK

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    George Manoussakis. An output sensitive algorithm for maximal clique enumeration in sparse graphs. International Symposium on Parameterized and Exact Computation, Sep 2017, Vienna, Austria. ⟨hal-01687111⟩

    GALaC

    Année de publication

  • Pré-publication, Document de travail

    Florent Hivert, Vincent Pilaud. Signaletic operads. 2019. ⟨hal-02997608⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Florent Hivert, Vincent Pilaud. Signaletic operads. FPSAC 2020 – 32nd International Conference on Formal Power Series and Algebraic Combinatorics, Jul 2020, online, France. pp.#6. ⟨hal-02997738⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Article dans une revue

    Bérénice Delcroix-Oger, Florent Hivert, Patxi Laborde-Zubieta, Jean-Christophe Aval, Adrien Boussicault. Non-Ambiguous Trees: new results and generalisation (Full version). European Journal of Combinatorics, 2021, 95, pp.103331. ⟨hal-03165269v2⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Article dans une revue

    Johanne Cohen, A. Fauquette, Jean-Michel Fourneau, G.C. Noukela, N. Pekergin. Convex Stochastic Bounds and Stochastic Optimisation on Graphs. Electronic Notes in Theoretical Computer Science, 2018, 337, pp.23 – 44. ⟨10.1016/j.entcs.2018.03.032⟩. ⟨hal-01832118⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Shaull Almagor, Nathann Cohen, Guillermo A. Pérez, Mahsa Shirmohammadi, James Worrell. Coverability in 1-VASS with Disequality Tests. 31st International Conference on Concurrency Theory, CONCUR 2020, Aug 2020, Vienna, Austria. pp.38:1–38:20, ⟨10.4230/LIPIcs.CONCUR.2020.38⟩. ⟨hal-03064637⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Albane Saintenoy, Emmanuel Léger, Christophe Grenier, N.M. Thiéry. Perspectives in Ground-Penetrating Radar at High Latitudes: From Occasional Imaging to Automated Continuous Monitoring. NSG2021 27th European Meeting of Environmental and Engineering Geophysics – Near Surface Geoscience’21, Aug 2021, Bordeaux & Online, France. pp.1-5, ⟨10.3997/2214-4609.202120205⟩. ⟨hal-04455388⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Thèse

    Jonathan Raiman. DeepType: compréhension du langage naturel par l’abstraction. Informatique [cs]. Université Paris-Saclay (2020-..), 2023. Français. ⟨NNT : ⟩. ⟨tel-04454479⟩

    GALaC

    Année de publication

  • Thèse

    Loric Duhaze. Problème d’accessibilité de marches de rotors dans des graphes. Informatique [cs]. Université Paris-Saclay (2020-..), 2023. Français. ⟨NNT : ⟩. ⟨tel-04454463⟩

    GALaC

    Année de publication

  • Article dans une revue

    Léo Kulinski, Josué Moreau. Jonglerie Musicale : Quand les notes de musiques subissent la gravité. Pousses de chercheurs & chercheuses, 2023, 1, pp.6-7. ⟨hal-04449632⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Article dans une revue

    Florent Hivert, Nefton Pali. Multiple Lie Derivatives and Forests. Advances in Mathematics, 2019, 354, ⟨10.1016/j.aim.2019.106732⟩. ⟨hal-02349044⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Pré-publication, Document de travail

    Jonas Sénizergues. Minimum colored maximum matching is NP-hard on trees. 2018. ⟨hal-01827567⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Article dans une revue

    Florent Hivert, Thiéry M. Nicolas. Controlling the C3 Super Class Linearization Algorithm for Large Hierarchies of Classes. Order, 2022, ⟨10.1007/s11083-022-09607-5⟩. ⟨hal-04414603⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Pré-publication, Document de travail

    Hugo Mlodecki. Decompositions of packed words and self duality of Word Quasisymmetric Functions. 2022. ⟨hal-03725331⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Pierre Bergé, Jason Crampton, Gregory Gutin, Rémi Watrigant. The Authorization Policy Existence Problem. CODASPY: Conference on Data and Application Security and Privacy, Mar 2017, Scottsdale, United States. pp.163-165, ⟨10.1145/3029806.3029844⟩. ⟨hal-01995978⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Zakaria Gheid, Yacine Challal, Lin Chen. Private and Efficient Set Intersection Protocol For RFID-Based Food Adequacy Check. IEEE WCNC, Apr 2018, Barcelone, Spain. ⟨hal-01786000⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Thèse

    Joël Gay. Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups. Discrete Mathematics [cs.DM]. Université Paris Saclay (COmUE), 2018. English. ⟨NNT : 2018SACLS209⟩. ⟨tel-01861199⟩

    GALaC

    Année de publication

    Disponible en libre accès

Logiciels