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 à firstname.lastname@example.org 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 :
Vendredi 21 avril 2017 - Vacances.
Vendredi 28 avril 2017 - On augmenting matchings via bounded-length augmentations - Julien Bensmaïl (I3S, Nice).
In a graph, it is well-known that a matching can be turned into a bigger matching by applying a so-called augmentation operation. Due to a classical result of Berge, by repeatedly applying this operation, we actually necessarily end up with a maximum matching. Nisse, Salch and Weber considered the influence on this fact of restricting the length k of the augmented paths. In particular, they proved that, for k=3, reaching, via augmentations of (≤k)-paths, a maximum matching from an initial matching can be done in polynomial time for any graph, while the same problem for any odd k≥5 is NP-complete. The latter result remains true for bipartite graphs, while we still have no clue for trees. Nisse, Salch and Weber nevertheless exhibited a polynomial-time algorithm solving this problem for any path. In a recent work with Garnero and Nisse, we made some progress towards understanding this problem for general trees. In particular, we have exhibited polynomial-time solving algorithms for a few more tree classes, including bounded-degree trees, caterpillars, subdivided stars, and trees where the vertices with degree at least 3 are sufficiently far apart. We have also obtained some negative results for modified versions of the problem. During this talk, we will present the proofs of some of these results, and mention some remaining open questions.