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 : LaBRI, LIRMM, 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

    Hugo Mlodecki. Décompositions des mots tassés et auto-dualité de l'algèbre des fonctions quasi-symétriques en mots. Combinatoire [math.CO]. Université Paris-Saclay, 2022. Français. ⟨NNT : 2022UPASG088⟩. ⟨tel-03926980⟩

    GALaC

    Année de publication 2022

    Disponible en libre accès

  • Pré-publication, Document de travail

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

    GALaC

    Année de publication 2022

    Disponible en libre accès

  • Pré-publication, Document de travail

    Benjamin Hellouin de Menibus, Silvère Gangloff, Piotr Opocha. Short-range and long-range order: a transition in block-gluing behavior in Hom shifts. 2022. ⟨hal-03842725⟩

    GALaC

    Année de publication 2022

    Disponible en libre accès

  • Communication dans un congrès

    Olivier Hudry, Irene Charon, Antoine Lobstein. Dominating, Locating-Dominating and Identifying Codes in the q-ary Lee Hypercube. 11th International Colloquium on Graph Theory and Combinatorics (ICGT 2022), 2022, Montpellier, France. ⟨hal-03744673⟩

    GALaC

    Année de publication 2022

  • Pré-publication, Document de travail

    Laurence Pilard, Johanne Cohen, Georges Manoussakis, Devan Sohier. A self-stabilizing algorithm for maximal matching in link-register model in $O(nDelta^3)$ moves. 2018. ⟨hal-01758068⟩

    GALaC

    Année de publication 2018

    Disponible en libre accès

  • Pré-publication, Document de travail

    Laurence Pilard, Johanne Cohen, Georges Manoussakis, Devan Sohier. A self-stabilizing algorithm for maximal matching in link-register model in $O(nDelta^3)$ moves. 2018. ⟨hal-01758068⟩

    GALaC

    Année de publication 2018

    Disponible en libre accès

  • Communication dans un congrès

    Thiéry M. Nicolas, Paul-Olivier Dehaye, Michael Kohlhase, Alexander Konovalov, Samuel Lelièvre, et al.. Interoperability in the OpenDreamKit Project: The Math-in-the-Middle Approach. CICM'16, Jul 2016, Białystok, Poland. ⟨10.1007/978-3-319-42547-4_9⟩. ⟨hal-01611491⟩

    GALaC

    Année de publication 2016

    Disponible en libre accès

  • Article dans une revue

    Lin Chen, Kaigui Bian. Neighbor Discovery in Mobile Sensing Applications: A Comprehensive Survey. Ad Hoc Networks, Elsevier, 2016, 48, pp.38 – 52. ⟨10.1016/j.adhoc.2016.05.005⟩. ⟨hal-01418383⟩

    GALaC

    Année de publication 2016

  • Article dans une revue

    Michele Mangili, Jocelyne Elias, Fabio Martignon, Antonio Capone. Optimal Planning of Virtual Content Delivery Networks under Uncertain Traffic Demands. Computer Networks, Elsevier, 2016, 106, pp.186-195. ⟨10.1016/j.comnet.2016.06.035⟩. ⟨hal-01338680⟩

    GALaC

    Année de publication 2016

    Disponible en libre accès

  • Communication dans un congrès

    Jean-Claude Bermond, Nathann Cohen, David Coudert, Dimitrios Letsios, Ioannis Milis, et al.. Bin Packing with Colocations. 14th International Workshop on Approximation and Online Algorithms (WAOA), Aug 2016, Aarhus, Denmark. pp.40-51, ⟨10.1007/978-3-319-51741-4_4⟩. ⟨hal-01435614⟩

    GALaC

    Année de publication 2016

    Disponible en libre accès

  • Article dans une revue

    Frédéric Chapoton, Florent Hivert, Jean-Christophe Novelli. A set-operad of formal fractions and dendriform-like sub-operads. Journal of Algebra, Elsevier, 2016, 465, pp.322-355. ⟨10.1016/j.jalgebra.2016.07.001⟩. ⟨hal-00839697⟩

    GALaC

    Année de publication 2016

    Disponible en libre accès

  • Article dans une revue

    Olivier Hudry, Antoine Lobstein. More Results on the Complexity of Domination Problems in Graphs. International Journal of Information and Coding Theory, Inderscience, 2017, 4 (2/3), pp.129-144. ⟨10.1504/ijicot.2017.083829⟩. ⟨hal-01593750⟩

    GALaC

    Année de publication 2017

  • Communication dans un congrès

    Marie Laveau, George Manoussakis, Joffroy Beauquier, Thibault Bernard, Janna Burman, et al.. Self-stabilizing Distributed Stable Marriage. International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2017, Boston, United States. pp.46-61, ⟨10.1007/978-3-319-69084-1_4⟩. ⟨hal-01576055⟩

    GALaC

    Année de publication 2017

    Disponible en libre accès

  • Pré-publication, Document de travail

    Laurence Pilard, Johanne Cohen, Georges Manoussakis, Devan Sohier. A self-stabilizing algorithm for maximal matching in link-register model in $O(nDelta^3)$ moves. 2018. ⟨hal-01758068⟩

    GALaC

    Année de publication 2018

    Disponible en libre accès

  • Article dans une revue

    Arvind Ayyer, Anne Schilling, Benjamin Steinberg, Nicolas M. Thiéry. Markov chains, $mathscr R$-trivial monoids and representation theory. International Journal of Algebra and Computation (IJAC), 2015, pp.1540008. ⟨10.1142/s0218196715400081⟩. ⟨hal-01121178⟩

    GALaC

    Année de publication 2015

    Disponible en libre accès

  • Article dans une revue

    Nathann Cohen, David Coudert, Guillaume Ducoffe, Aurélien Lancin. Applying clique-decomposition for computing Gromov hyperbolicity. Theoretical Computer Science, Elsevier, 2017, 690, pp.114-139. ⟨10.1016/j.tcs.2017.06.001⟩. ⟨hal-01540756⟩

    GALaC

    Année de publication 2017

    Disponible en libre accès

  • Article dans une revue

    Michele Mangili, Fabio Martignon, Stefano Paris, Antonio Capone. Bandwidth and Cache Leasing in Wireless Information Centric Networks: a Game Theoretic Study. IEEE Transactions on Vehicular Technology, Institute of Electrical and Electronics Engineers, 2017, 66 (1), pp.679-695. ⟨10.1109/tvt.2016.2547740⟩. ⟨hal-01293897⟩

    GALaC

    Année de publication 2017

    Disponible en libre accès

  • Article dans une revue

    Arvind Ayyer, Anne Schilling, Benjamin Steinberg, Nicolas M. Thiéry. Markov chains, $mathscr R$-trivial monoids and representation theory. International Journal of Algebra and Computation (IJAC), 2015, pp.1540008. ⟨10.1142/s0218196715400081⟩. ⟨hal-01121178⟩

    GALaC

    Année de publication 2015

    Disponible en libre accès

  • Communication dans un congrès

    Yitu Wang, Wei Wang, Lin Chen, Zhaoyang Zhang. Lexicographic Relay Selection and Channel Allocation for Multichannel Cooperative Multicast. IEEE WCNC, Mar 2017, San Francisco, United States. ⟨hal-01618064⟩

    GALaC

    Année de publication 2017

  • Autre publication

    Olivier Hudry, Antoine Lobstein. On the Complexity of the Uniqueness of Solutions in Graph Problems. 2017. ⟨hal-01613394⟩

    GALaC

    Année de publication 2017

Logiciels