ALGCO Team : Algorithms, Graphs and Combinatorics – LIRMM

Emeric GIOAN

Head

ALGCO Team

Algorithms, Graphs and Combinatorics

Research of the AlGCo team (Algorithms, Graphs and Combinatorics) is focused on theoretical and algorithmic investigations of classical combinatorial structures: mainly graphs, but also signed graphs, directed graphs, matroids, oriented matroids… Our motivations are fundamental (questions about partitioning, coloring, embedding, isomorphisms, bijections…), algorithmic (notably related to parametrized complexity: fixed-parameter-tractable algorithms, existence of polynomial kernels), or applied in connection with other domains (computational biology, imaging, morphometry, network modelization, data science, artificial intelligence…).

Members

Staff
Emeric Gioan, Chargé de recherche, CNRS
Mathieu Mari, , UM
Daniel Gonçalves, Chargé de recherche, CNRS
Dimitrios Thilikos Touloupas, Directeur de recherche, CNRS
Mickael Montassier, Professeur des universités, UM
Alexandre Pinlou, Professeur des universités, UM
Stephane Bessy, Professeur des universités, UM
Marin Bougeret, Maître de conférences, UM
William Lochet, Chargé de recherche, CNRS
Christophe Paul, Directeur de recherche, CNRS
Philippe Janssen, Maître de conférences, UM
Petru Valicov, Maître de conférences, UM
Pascal Ochem, Chargé de recherche, CNRS
Ignasi Sau, Chargé de recherche, CNRS
Nicolas Serrurier Gourvès, Adjoint technique, UM

Associates & Students
Giannos Stamoulis, UM
Hugo Jacob, UM
Gaetan Berthe, UM
Laure Morelle, UM
Evangelos Protopapas, CNRS
Yann Marin, UM
Amadeus Reinald, UM

Regular Co-workers

October 2023

Thursday 5 October

10 h 00 min – 10 h 30 min: Timothé Picavet , «A parameterized approximation scheme for the 2D-Knapsack problem with wide items»
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA’19] showed that it is also W[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. We make progress towards this goal by showing a PAS under the following assumptions: 1. both the box and all the input rectangles have integral, polynomially bounded sidelengths; 2. every input rectangle is wide — its width is greater than its height; and 3. the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.
https://info-web.lirmm.fr/collorg/8d024431-c6f8-4ebd-99b6-f201eeb01e2f
10 h 30 min – 11 h 00 min: Timothé Picavet, «Locally approximating dominating sets in K_{2,t}-minor-free graphs»
The field of distributed algorithms studies algorithms that are designed to run on different computers simultaneously, without any shared memory. We focus on the so-called LOCAL model, where computers are part of a network and work together to solve a problem (in our case Minimum Dominating Set) on the network itself. The LOCAL model is used to study the locality in network computing, to determine which problems can be solved when every computer only knows a part of the network (in our case a constant radius region) before outputting. As finding a constant-factor approximation of MDS is not possible on general graphs, we will focus on minor forbidden classes, particularly the class of $K_{2,t}$-minor-free graphs. We give a $(2t-1)$-approximation for MDS on this class, which breaks the non-exponential approximation factor barrier. This also generalizes and simplifies the involved proof of the 5 approximation factor for outerplanar graphs.
https://info-web.lirmm.fr/collorg/5d603080-de4c-4033-b809-755fdae5693c

Thursday 12 October

10 h 00 min – 11 h 00 min: Laure Morelle, «TBA»
TBA
https://info-web.lirmm.fr/collorg/572604ed-e4ca-4dcd-b400-b8da1955d6c6

Thursday 19 October

10 h 00 min – 11 h 00 min: Christophe Paul, «Linear time modular decomposition algorithm»
There is a long history of modular decomposition algorithms starting in the 70’s with a $O(n^4)$ algorithm. The first linear time algorithms appeared in 1994 (by Cournier, Habib and by McConnell, Spinrad). Since them simplified (almost) linear time algorithms have been proposed. I will describe one based on LexBFS and a tree-partition refinement technique. The complexity analysis requires a carefully amortized analysis that we will discuss.

This is a joint work with D. Corneil, M. Habib and M. Tedder that was originally presented at ICALP’08, but which full version is still lacking.
https://info-web.lirmm.fr/collorg/26d0a0a7-e10c-4b9c-908b-626b259d4681

Thursday 26 October

10 h 00 min – 11 h 00 min: Ignasi Sau, «On the number of labeled graphs of bounded clique-width»
Clique-width is a graph parameter that has become quite popular due, in particular, to the nice algorithmic properties of the class of graphs for which this parameter is bounded by a constant. In this talk we address the following combinatorial question: which is the (asymptotic) number of $n$-vertex labeled graphs with clique-width at most $k$? We provide lower and upper bounds that leave a quite narrow gap, both for clique-width and for its linear variant. One of our main results is that the number of $n$-vertex labeled graphs with clique-width at most $k$ is $2^{O(kn)}n!$, which is a considerable improvement over the previously best known upper bound $2^{O(k^2 n)}n!$.

Joint work with Marc Noy, Clément Requilé and Giannos Stamoulis.
https://info-web.lirmm.fr/collorg/3d2a7200-963d-4bbc-aefb-c7cdd4587650

November 2023

Thursday 23 November

10 h 00 min: Evangelos Protopapas, «TBA»
TBA
https://info-web.lirmm.fr/collorg/2cc812e1-fbfa-4df5-9e8a-718f29ee397a

We use cookies to ensure that we give you the best experience on our website. We do not call on third party commercial services therefore third party cookies are NOT used.
Nous utilisons des traceurs nécessaires au bon fonctionnement du site , cependant nous n'utilisons PAS de traceurs publicitaires.