AlGCo : algorithms, graphs and combinatorics
| Computer science department - LIRMM |
French version here
Welcome
The AlGCo team focuses on graph theory, and more generally algorithmic problems and
combinatorial structures.
Actually, our main research specialities are:
- Graph decompositions, exact and fixed parameter tractable algorithms, kernelization
(ANR-JCJC project Elit 2021/2025, see here - Regional project Kernel 2012/2015, here - ANR project Agape 2009/2013, here - ANR project Graal 2006/2009, here)
Graph decomposition techniques
(tree, branch, modular, split), and their possible corresponding parameters (tree-width, branch-width, rank-width...) are important for various reasons.
First, graph decomposition is often used as a pre-processing step to solve a given problem. Secondly, from an algorithmic point of view, decomposing a graph allows for algorithms
that deal with the components and their structure separately. In particular, the corresponding parameter can measure the quality of the decomposition, which provides low complexity algorithms
when this parameter is bounded. Finally, those decompositions often rely on (or highlight) interesting combinatorial properties that can be extended to more general structures.
Fixed parameter algorithms and the corresponding fixed parameter tractability (FPT) aim at studying exact exponential algorithms. It provides a complexity analysis that is more subtle
than the standard one, as it takes into account not only the size of the input, but also an associated parameter (for example some decomposition parameters, as mentioned above).
The grail is to find a parameter k such that solving a problem of input size n is of the form O(f(k).n), for some function f.
La génération croissante de grandes masses de données est un phénomème commun à de nombreuses discplines scientifiques
(biologie, physique, sciences de lenvironnement
)
L'exploitation de ces données requière des traitements informatiques systématiques allant du stockage,
de la fouille des données à l'optimisation et donc l'algorithmique. Les techniques de pré-traitement sont depuis toujours à la base des méthodes heuristiques.
Ce n'est pourtant qu'aux alentours de 2005 que la théorie de la kernelisation offre un cadre formel pour leur étude.
Jusqu'ici essentiellement appliquée à des problèmes issus de la théorie des graphes,
nous étendrons le champs de la kernelisation à d'autres domaines d'applications à l'interface de l'informatique.
Nos objectifs seront aussi de compléter cette théorie du point vue de la complexité algorithmique (bornes, limites).
- Graphs in topological structures, combinatorial maps, embedded graphs and their oriented structures
(ANR project Gato 2016/2020, here - ANR project Egos 2012/2015, here - ANR projet Gratos 2009/2012, here)
It corresponds to the study of interactions between graph theory and structures, problems or models of topological nature:
graphs embedded on surfaces (notably planar graphs, which represent the base case of many algorithmic and combinatorial problems),
graphs defined as the intersection of geometrical objects,
graph invariants that characterize their topological properties,
parallels with more general topological structures (simplicial complexes, matroids and their duals, polytopes), etc.
In the plane, many families of graphs have oriented structures, which are orientations and
colorings of the edges of the graph satisfying a particular local property. For example: 2-connected bipartite planar graphs admit 2-orientations, 3-connected planar graphs admit Schnyder woods, 4-connected planar triangulations admit transversal structures. These
structures are in bijection with several combinatorial objects like contact system of polygons,
TD-Delaunay triangulations, or Dyck words. They also appear to have various computer
science applications such as succinct encoding, graph drawing, graph spanners, etc.
This project aims at generalizing these oriented structures to higher genus surfaces and
higher dimensional objects.
- General theory of graphs and their refinements
(ANR project Digraphs 2020/2024, here - ANR project Hosigra 2018/2022, here)
Directed graphs, signed graphs, colored graphs...
- Matroids and oriented matroids, mathematical theory and interdisciplinary applications
(Regional project Omsmo 2016/2021, here - ANR project Teomatro 2010/2014, here)
The theory of matroids and oriented matroids generalizes the theory of graphs as space cycles, can be seen as a combinatorial abstraction of linear algebra,
and provides an appropriate langage for incidency and convexity relations in several geometrical and topological objects:
point configurations, polytopes, arrangements of lines, pseudolines, hyperplanes, pseudohyperplanes, pseudospheres...
It is a natural theoretical setting for various combinatorial notions (duality in graphs and linear programming, Tutte polynomial, etc.).
An application is actually developped for a combinatorial encoding of model shapes based on these structures.
The aim is to develop a theory and a computer tool for the analysis/comparison/classification of shapes of 2D/3D landmark based models, for application to various areas: clinical imagery, physical anthropolgy...
contact AlGCo webmaster
|