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

  • Pré-publication, Document de travail

    Quentin Japhet, Dimitri Watel, Dominique Barth, Marc-Antoine Weisser. Maximal Line Digraphs. 2024. ⟨hal-04587485v2⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Thèse

    Jie Hu. Rainbow subgraphs and properly colored subgraphs in colored graphs. Combinatorics [math.CO]. Université Paris-Saclay, 2022. English. ⟨NNT : 2022UPASG045⟩. ⟨tel-04588976⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Thèse

    Jonathan Raiman. DeepType : Natural Language Understanding by Abstraction. Artificial Intelligence [cs.AI]. Université Paris-Saclay, 2023. English. ⟨NNT : 2023UPASG016⟩. ⟨tel-04588554⟩

    AO, GALaC

    Année de publication

    Disponible en libre accès

  • Article dans une revue

    Olivier Hudry, Ville Junnila, Antoine Lobstein. On Iiro Honkala’s contributions to identifying codes. Fundamenta Informaticae, In press. ⟨hal-04568130⟩

    GALaC

    Année de publication

  • Pré-publication, Document de travail

    Ylène Aboulfath, Dimitri Watel, Marc-Antoine Weisser, Thierry Mautor, Dominique Barth. Maximizing minimum cycle bases intersection. 2024. ⟨hal-04559959⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Communication dans un congrès

    Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, et al.. The Grid-Minor Theorem Revisited. SODA 2024 – 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 2024, Westin Alexandria Old Town, United States. pp.1241-1245, ⟨10.1137/1.9781611977912.48⟩. ⟨hal-04553168⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Article dans une revue

    Marcin Briański, Jędrzej Hodor, Hoang La, Piotr Micek, Katzper Michno. Boolean Dimension of a Boolean Lattice. Order, 2024. ⟨hal-04553148⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • Pré-publication, Document de travail

    Lech Duraj, Ross J. Kang, Hoang La, Jonathan Narboni, Filip Pokrývka, et al.. The $chi$-binding function of $d$-directional segment graphs. 2024. ⟨hal-04553176⟩

    GALaC

    Année de publication

    Disponible en libre accès

  • 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

Logiciels