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

  • Pré-publication, Document de travail

    Pierre Béaur, Benjamin Hellouin de Menibus. Sturmian and infinitely desubstitutable words accepted by an ω-automaton. 2023. ⟨hal-04034705⟩

    GALaC

    Year of publication

    Available in free access

  • Pré-publication, Document de travail

    Cesar Ceballos, Viviane Pons. The s-weak order and s-permutahedra I: combinatorics and lattice structure. 2023. ⟨hal-04024015⟩

    GALaC

    Year of publication

    Available in free access

  • Pré-publication, Document de travail

    Benjamin Hellouin de Menibus, Victor H Lutfalla, Camille Noûs. The Domino problem is undecidable on every rhombus subshift. 2023. ⟨hal-04004801⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Vincent Pilaud, Viviane Pons, Daniel Tamayo Jiménez. Permutree sorting. FPSAC 2021 – 33rd International Conference on Formal Power Series and Algebraic Combinatorics, Jan 2022, Ramat Gan, Israel. pp.#31. ⟨hal-03451389⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Jean-Claude Bermond, Johny Bond, Jean-François Saclé. Large hypergraphs of diameter one. Graph theory and Combinatorics, Academic Press, 1984, Cambridge, United Kingdom. pp.19-28. ⟨hal-02447161⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Florent Hivert, Anne Schilling, Nicolas M. Thiéry. The biHecke monoid of a finite Coxeter group and its representations. Algebra & Number Theory, 2013, 7 (3), pp.595–671. ⟨10.2140/ant.2013.7.595⟩. ⟨hal-00632266⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Tullio Ceccherini-Silberstein, Michel Coornaert, Francesca Fiorenzi, Zoran Sunic. Cellular automata between sofic tree shifts. Theoretical Computer Science, 2013, 506, pp.79-101. ⟨10.1016/j.tcs.2013.07.007⟩. ⟨hal-00946150⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Evelyne Flandrin, Antoni Marczyk, Jakub Przybylo, Jean-François Saclé, Mariusz Woźniak. Neighbor Sum Distinguishing Index. Graphs and Combinatorics, 2013, 29 (5), pp.1329-1336. ⟨10.1007/s00373-012-1191-x⟩. ⟨hal-01753341⟩

    GALaC

    Year of publication

    Available in free access

  • Article dans une revue

    Maurice Pouzet, Nicolas M. Thiéry. Some relational structures with polynomial growth and their associated algebras I: Quasi-polynomiality of the profile. The Electronic Journal of Combinatorics, 2013, 20 (2), 35pp. ⟨hal-01121195v2⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Stefano Paris, Fabio Martignon, Ilario Filippini, Lin Chen. A Bandwidth Trading Marketplace for Mobile Data Offloading. IEEE Infocom 2013 (mini conference), Apr 2013, Torino, Italy. ⟨hal-01724605⟩

    GALaC

    Year of publication

  • Communication dans un congrès

    Antimo Barbato, Antonio Capone, Lin Chen, Fabio Martignon, Stefano Paris. A Power Scheduling Game for Reducing the Peak Demand of Residential Users. IEEE GreenComm 2013 (IEEE Conference on Green Communications), Oct 2013, Online conference, United States. ⟨hal-01724609⟩

    GALaC

    Year of publication

  • HDR

    Sylvie Delaët. Auto-stabilisation : Solution Elégante pour Lutter contre Les Fautes. Informatique [cs]. Université Paris Sud – Paris XI, 2013. ⟨tel-01742088⟩

    GALaC

    Year of publication

    Available in free access

  • Communication dans un congrès

    Michele Mangili, Fabio Martignon, Antonio Capone. A Comparative Study of Content-Centric and Content-Distribution Networks: Performance and Bounds. IEEE Globecom 2013, Dec 2013, Atlanta, United States. ⟨hal-01724596⟩

    GALaC

    Year of publication

  • Communication dans un congrès

    Michele Mangili, Fabio Martignon, Antonio Capone, Stefano Paris. Efficient Joint Bandwidth and Cache Leasing in Information Centric Networks. IEEE Globecom 2013, Dec 2013, Atlanta, United States. ⟨hal-01724600⟩

    GALaC

    Year of publication

  • Communication dans un congrès

    Antimo Barbato, Lin Chen, Fabio Martignon, Stefano Paris. A Multi-Armed Bandit Formulation for Distributed Appliances Scheduling in Smart Grids. IEEE GreenComm 2014 (IEEE Conference on Green Communications), 2014, Online, United States. ⟨hal-01109073⟩

    GALaC

    Year of publication