GALaC

Graphs, Algorithms and Combinatorics (GALaC)

The GALAC team gathers LISN researchers working on combinatorics, algorithms, graph theory, networked and distributed systems. More precisely, our research areas are the following: our combinatorics research focuses on the strong interactions and relationships between algorithms and algebraic structures, and our graph theory research on structural properties and decomposition problems. Efficient algorithms and models for networked systems are developed in the third activity of the team, using the formalism of game theory and distributed computing.

Research themes

The GALaC team has three main research themes.

The main goal of this group is to design, model, study the control and performance of algorithms designed specifically for distributed systems and their applications. The scientific contribution we aim at is both theoretical with the development of new mathematical models and quality proofs and also applied with the development of innovative tools for different types of networks (opportunistic, content-centric or congitive).

More precisely, the objectives of the ANS group (for Algorithms for Networked systems) are:

  • To establish basic building blocks for the design and optimization of networked systems. This includes control theory, game theory, distributed algorithms and especially self-stabilization and fault tolerance as well as simulation of systems via discrete event models.
  • To design efficient algorithms and protocols based on the development of theoretical frameworks, and to evaluate their performance through practical scenarios. This includes opportunistic wireless networks (e.g., robot networks, ad hoc wireless networks, sensor networks), future infrastructure and protocols for the Internet (information, content-centric networks), security and safety in cyber-physical systems.

The collaborations of this axis take place on the 5 continents.

The main interest of this activity is the study of the relationship between algebraic structures and algorithms. The researchers are particularly interested in the following topics:

  • Algebraic structures (combinatorics of Hopf algebras, Operads, Monoids, ...) related to algorithms;
  • Enumerative combinatorics and symbolic dynamics.
  • Object-oriented software designed for mathematical modeling, in particular the development of the SageMath software;

More precisely, the research projects are related to algebraic combinatorics, are at the interface of enumerative combinatorics and concern the analysis of algorithms from the point of view of symbolic and algebraic computations. The objectives are twofold: first, thanks to a massive generalization of the notion of generating series we hope to propose a theoretical framework allowing the study of the fine behavior of many different algorithms and second, and in a reciprocal way, the study of the same algorithms opens up new avenues for the discovery of objects or algebraic identities of interest. These identities have several applications in mathematics, in particular in representation theory but also in physics (mainly in statistical physics).

The research is largely based on computer experimentation, with a significant amount of development via the Sage-Combinat software project.

However, the level of sophistication, flexibility and quality of the required computational tools has reached a point where, on a large scale, collaborative development is essential. The design and collaborative development of such software raises the search for quality. The challenges are both in the domain of computer science and around the mathematical modeling and management of a large hierarchy of (object-oriented) classes, etc.

These specific questions also raise more general combinatorial questions. It is then envisaged to work on enumerative combinatorics, cellular automata and in particular trees.

This axis feeds regular collaborations in France but also with Germany, North America and India.

The main focus is on structural and algorithmic issues. The team has established an expertise including problems such as finding large cycles of a given graph, coloring a graph, solving covering problems, or advancing graph theory by finding extreme graphs satisfying a constraint.

The generalization of some problems is also considered for edge or colored vertex graphs. For example, colored covering graphs have been studied for colored edge or vertex graphs. Alternatively it has been searched the dominant set in a graph having at least one vertex of each color. Beyond the purely theoretical interest these approaches have a great interest in the field of bioinformatics as well as in that of the Web.

Many of the questions we consider can also be stated in terms of linear optimization. This opens perspectives.

We have many collaborations with French groups: LaBRILaboratoire Bordelais de Recherche en Informatique, LIRMMLaboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, LIAFALaboratory of Algorithmic Computing: Foundations and Applications and LIMOSLaboratory of Computing, Modeling and Optimization of Systems as well as in Europe, in North and South America and mainly in Asia with China, Japan, India

Coordination

Team

Last publications

  • Thèse

    Daniel Tamayo Jiménez. Combinatorics of permutreehedra and geometry of s-permutahedra. Combinatorics [math.CO]. Université Paris-Saclay, 2023. English. ⟨NNT : 2023UPASG066⟩. ⟨tel-04302406⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Dominique Barth, Thierry Mautor, Dimitri Watel, Marc-Antoine Weisser. Configuring an heterogeneous smartgrid network: complexity and approximations for tree topologies. Journal of Global Optimization, 2023, ⟨10.1007/s10898-023-01338-0⟩. ⟨hal-04289472⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Nathalie Aubrun, Nicolás Bitar, Sacha Huriot-Tattegrain. Strongly aperiodic SFTs on generalized Baumslag–Solitar groups. Ergodic Theory and Dynamical Systems, 2023, pp.1-30. ⟨10.1017/etds.2023.44⟩. ⟨hal-04284393⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Nathalie Aubrun, Nicolas Bitar. Domino Snake Problems on Groups. Fundamentals of Computation Theory, Sep 2023, Trier, Germany. pp.46-59, ⟨10.1007/978-3-031-43587-4_4⟩. ⟨hal-04284389⟩

    GALaC

    Year of publication

    Available in free access

  • Pré-publication, Document de travail

    Benjamin Hellouin de Menibus, Rémi Pallen. Two-player Domino games. 2023. ⟨hal-04265421⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Balthazar Charles. A Description of the Minimal Elements of Shi Regions in Classical Weyl Groups. 34th Conference on Formal Power Series and Algebraic Combinatorics, IISc, Jun 2022, Bangalore, India. ⟨hal-04258739⟩

    GALaC

    Year of publication

    Available in free access

  • Thèse

    Tianjiao Dai. Some vertex colouring problems and a generalisation of Hamilton-connectivity in graphs. Discrete Mathematics [cs.DM]. Université Paris-Saclay, 2023. English. ⟨NNT : 2023UPASG067⟩. ⟨tel-04259639⟩

    GALaC

    Year of publication

    Available in free access

  • 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. INISTA, Sep 2023, Hammamet, Tunisia. ⟨10.48550/arXiv.2306.10950⟩. ⟨hal-04244934⟩

    AO, GALaC, LaHDAK

    Year of publication

  • Communication dans un congrès

    Eoin Hurley, François Pirot. Uniformly Random Colourings of Sparse Graphs. STOC ’23: 55th Annual ACM Symposium on Theory of Computing, Jun 2023, Orlando FL USA, France. pp.1357-1370, ⟨10.1145/3564246.3585242⟩. ⟨hal-04245446⟩

    GALaC

    Year of publication

    Available in free access

  • Pré-publication, Document de travail

    Quentin Chuet, Johanne Cohen, François Pirot. Acyclic colourings of graphs with obstructions. 2023. ⟨hal-04245454⟩

    GALaC

    Year of publication

  • Pré-publication, Document de travail

    Tianjiao Dai, Qiancheng Ouyang, François Pirot. New bounds for odd colourings of graphs. 2023. ⟨hal-04245451⟩

    GALaC

    Year of publication

  • Proceedings/Recueil des communications

    Johanne Cohen, Laurence Pilard, Jonas Sénizergues, Mikaël Rabie. Making Self-Stabilizing Algorithms for Any Locally Greedy Problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, ⟨10.4230/LIPIcs.SAND.2023.11⟩. ⟨hal-04214291⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Kehao Wang, Lin Chen, Quan Liu, Khaldoun Al Agha. On Optimality of Myopic Sensing Policy with Imperfect Sensing in Multi-Channel Opportunistic Access. IEEE Transactions on Communications, 2013, 61 (9), pp.3854-3862. ⟨10.1109/TCOMM.2013.071213.120573⟩. ⟨hal-01761109⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Loïc Le Mogne, Viviane Pons. Deficit and (q, t)-symmetry in triangular Dyck paths. 35th Formal Power Series and Algebraic Combinatorics, FPSAC 2023, Jul 2023, Davis CA, United States. pp.#21. ⟨hal-04191164⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Olivier Hudry, Antoine Lobstein. Some Complexity Considerations on the Uniqueness of Graph Colouring. WSEAS Transactions on Mathematics, 2023, 22, pp.483-493. ⟨hal-04178848⟩

    GALaC

    Year of publication