Combinatorics and Algorithms
Head : J.-F. MarckertMembers Publications

The goal of combinatorics is the study of discrete structures. These appear in all sciences: biology, mathematics, physics, and of course computer science, where they play a special role; in fact, computers work with discrete objects only.

Thus, the file system in a computer, a data structure, the encoding of a DNA strand, a computer network, are combinatorial objects: trees, tables, words, graphs.

The Combinatorics and Algorithms team seeks to understand, describe, and sometimes define these structures. It also contributes to inventing, analyzing and optimizing the algorithms working on these objects. Among its specialties, there is the enumeration of structures, the study of graphs and distributed algorithms.

Research themes:

  • Enumerative and algebraic combinatorics
    • Head: P. Duchon
    • Keywords: enumeration, random and exhaustive generation, generating functions, bijections, maps, trees, sandpile model, random structures.
  • Graphs and Optimisation
    • Head: F.Kardoš
    • Keywords: routing in networks, compact data structures, Hamiltonicity, colouring, transmission index.
  • Distributed Algorithms
    • Head: A. Zemmari
    • Keywords: local computation, election, termination detection, recognisability, fibration, covering, probabilistic algorithm, systems of mobile agents.