Les GT se tiennent chaque vendredi de 14h à 15h en salle 178. Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Prochains exposés :

Lundi 25 mars 2019 14h - Low-depth decompositions of sparse graphs - Michał Pilipczuk (University of Warsaw).

Decomposition techniques are widely used in designing algorithms on sparse inputs, like planar graphs or graphs of bounded maximum degree. The idea is to cover the input structure with a relatively small number of well-behaved "pieces", so that the search for a global solution can be reduced to searching for a solution in each of the pieces separately. A classic application of this principle is the Baker's layering technique: for every k, every planar graph can be partitioned into k+1 parts so that any k of them induce a graph of treewidth O(k). During the talk we will describe a stronger type of decompositions, called low-treedepth decompositions or p-centered colorings. Here, the idea is that the well-behaved pieces should have bounded depth rather than width. This kind of decompositions is particularly useful for designing parameterized algorithms on sparse graphs, especially in the regimes of low space complexity and of distributed computing. Finally, we will sketch a proof that planar graphs admit p-centered colorings with O(p^19) colors; this part of the talk will be based on a joint work with Sebastian Siebertz, presented at SODA 2019.

Vendredi 29 mars 2019 - Containment - a Variation of Cops & Robber - Natasha Komarov (St Lawrence University, USA).

We consider "Containment"': a variation of the graph pursuit game of Cops and Robber in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop), and the cops win by "containing" the robber---that is, by occupying all of the edges incident with a vertex v while the robber is at v. We develop several bounds on the minimal number of cops required to contain a robber, in particular relating this number to the well-studied ``cop-number'' in the original Cops and Robber game. We discuss the containability and containment number of some specific families of graphs, including hypercubes and certain Cartesian products. Time permitting, we will conclude with some discussion of current conjectures and other directions for future work.


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar