8h40 | Welcoming (coffee) |
9h | Opening: presentation of the LEA STRUCO |
9h20 | Z. Dvořák: Algorithms for structurally sparse graphs |
10h30 | Coffee break |
10h45 | É. Balandraud: Addition Theorems via the Combinatorial Nullstellensatz |
11h40 | J. Sgall: Two-bounded-space bin packing revisited |
12h40 | Buffet at LIAFA (room 6A92 "sous-marin") |
14h10 | Sylvain Schmitz: Algorithmic aspects of well-quasi-orderings and applications to verification |
15h | Free time to meet and work |
16h | Coffee break |
All talks and coffee breaks are in room 1C18.
8h50 | Morning coffee |
9h15 | M. Habib: Multisweep graph algorithms |
10h15 | Coffee break |
10h40 | M. Loebl: Strength of graph polynomials |
11h30 | L. Viennot: Graph spanners and their relation to the girth conjecture |
12h30 | Lunch at the restaurant l'audiernes |
14h | Free time to meet and work |
16h | Closing coffee break |
All talks and coffee breaks are in room 1D06.
Many graph problems which are hard in general become easier (polynomial-time solvable, or at least fixed-parameter tractable or approximable) when restricted to specific graph classes. We give an overview of results of this form, with particular attention to techniques applicable to many different problems (algorithmic metatheorems) and techniques for structurally sparse graph classes (minor closed, having bounded expansion, nowhere dense).
The polynomial method has shown itself very efficient to prove generalizations and new results in many fields of combinatorics. In this talk, we will focus on additive combinatorics. We will explain the proofs of three addition theorems; Cauchy-Davenport, Dias da Silva-Hamidoune Theorem (Erdos-Heilbronn Conjecture) and a new result, which allows to answer to a conjecture of Selfridge.
We analyze approximation algorithms for bounded-space bin packing by comparing them against the optimal bounded-space packing (instead of comparing them against the globally optimal packing that does not necessarily satisfy the bounded-space constraint). For 2-bounded-space bin packing we construct a polynomial time offline approximation algorithm with asymptotic worst case ratio $3/2$, and we show a lower bound of $5/4$ for this scenario. We show that no 2-bounded-space online algorithm can have an asymptotic worst case ratio better than 4/3. (This is joint work with Marek Chrobak and Gerhard J. Woeginger.)
The talk presents an algebraic approach to proving complexity upper bounds on the length of controlled bad sequences in well-quasi-orderings. This leads to tight multiply-recursive upper bounds for verification problems proven decidable thanks to Highman's Lemma.
Graph searches are well-known and studied in many applications. One can consider graph search using their underlying tree structure or analyze the complexity of their implementation. Here we consider a graph search as a producer of a total ordering on the set of vertices (the order in which the vertices are visited by the search). This viewpoint has been recently very successful on classical search such as Generic, BFS, DFS, LexBFS... and their respective orderings have been characterized using a four vertices forbidden configuration.
In this talk we will present what we think is a promising direction for graph algorithms design. The main issue is to use a series of consecutive graph searches in order to solve an optimization problem on a graph. From one search to the other we only keep track of a total ordering of the vertices which can be used to break ties during the next search. Such a framework is very easy to implement and can be applied even on graphs of huge size. If the series of searches is bounded it yields a linear time algorithm but unfortunately despite its simplicity the main difficulty remains to prove such an algorithm.
Therefore this can be understood as a composition of graph searches using a kind of operator based on a tie-break rule. This leads to multi-sweep algorithms made up of a series of consecutive graph searches.
Up to my knowledge the first examples of multisweep algorithms were described for planarity testing, see Hopcroft and Tarjan (1974) and also de Fraysseix, Ossona de Mendes and Rosentiehl (2006). The 2-sweep Depth-first Search algorithm for the computation of strongly connected components by Kosaraju (1978) can also be put in this framework. Another recent interesting example is the 6 Lexicographic Breadth First Searches (LBFS) algorithm for interval graph recognition by Corneil, Olariu and Stewart (2010).
We will briefly present the tools we can play with and describe two new applications for : computing the diameter, and computing the minimum path cover of a co-comparability graph. We finish with some natural open problems.
We discuss graph polynomials, and in particular their role in the complexity of computation, and in the graph isomorphism problem.
Given a graph, a spanner is a subgraph somehow preserving distances. There is indeed a trade-off between the number of edges in the spanner and how much the distances are stretched compared to the graph. Sequential as well as parallel algorithms for computing spanners will be presented. The trade-off achieved is optimal if we admit the girth conjecture of Erdös.
The meeting takes places at LIAFA, which is situated at the corner of rue Chevaleret and Clisson, in the 13th district of Paris.
The entrance is situated at 6 rue Clisson
(there is an entrance at ``175 rue
du chevaleret`` but it is not available due to some reconstruction work).
The address is
LIAFA 6 rue Clisson 75013 Paris
The closest metro station is Chevaleret
, on line 6. Other close metro stops
are Bibliothèque François Mitterand
on line 14 and Campo-Formio
on line 5.
The bus number 27 has a stop called Clisson
, which is on rue Jeanne d'Arc,
slightly north to the corner of rue Jeanne d'Arc and rue Clisson.
Should you need it, the LIAFA's secretary office is situated on 7th Floor, "Plateau A", office 7A23.
Internet access will be ensured by two wireless networks:
There shall be signs indicating the way inside the building from the entrance
situated at 6 rue Clisson
.
Thursday
All talks and coffee breaks are in room 1C18 (1st floor, "Plateau C"). The buffet is in room 6A92 (6th floor, "Plateau A").
For convenience, the room 5D91 (5th floor, "Plateau D") is also reserved for the whole afternoon.
Friday
All talks and coffee breaks are in room 1D06 (1st floor, "Plateau D").
The restaurant l'audiernes is situated at
22 Rue Louise Weiss 75013 Paris
It's a five-minute walk away from LIAFA.
In case some signs are missing inside the building
If some signs are missing, just take one of the elevators
shortly after the entrance at 6 rue Clisson
. Go to the first floor and then follow either
"Plateau C" (on Thursday) or "Plateau D" (on Friday). It will only remain then
check for the right office number.
Pierre Aboulker (LIAFA, Université Paris 7) Éric Balandraud (Équipe combinatoire & optimisation, Université Paris 6) Ahmed Bouajjani (LIAFA, Université Paris 7) Patricia Bouyer (LSV, CNRS) Pierre Charbit (LIAFA, Université Paris 7) Jérémie Dusart (LIAFA, Université Paris 7) Zdeněk Dvořák (KAM, Univerzita Karlova) Peter Habermehl (LIAFA, Université Paris 7) Michel Habib (LIAFA, Université Paris 7) Frédéric Havet (MASCOTTE, CNRS) Andrea Jimenez (KAM, Univerzita Karlova) Florent Jouve (Département de mathématique, Université d'Orsay) Tomáš Kaiser (KMA, Západočeská Univerzita) František Kardoš (MASCOTTE, Univeristé de Nice-Sophia Antipolis) Daniel Kráľ (KAM, Univerzita Karlova) Martin Loebl (KAM, Univerzita Karlova) Lukáš Mach (KAM, Univerzita Karlova) Antoine Mamcarz (LIAFA, Université Paris 7) Jaroslav Nešetřil (KAM, Univerzita Karlova) Patrice Ossona de Mendez (CAMS, CNRS) Hana Polišenska (KAM, Univerzita Karlova) Sylvain Schmitz (LSV, ENS Cachan) Jean-Sébastien Sereni (LIAFA, CNRS) Jiří Sgall (KAM, Univerzita Karlova) Nicolas Trotignon (LIP, ENS Lyon) Laurent Viennot (LIAFA, INRIA) Tomáš Vojnar (DITS, Faculty of Information Technology of Brno) Jan Volec (KAM, Univerzita Karlova) Zelealem Yilma (LIAFA, Université Paris 7)