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 :

Vendredi 21 décembre 2018 - Sequential Metric Dimension (in trees) - Julien Bensmail (Université de Nice).

In the Localization Game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph G. At every step, one vertex v of G can be probed which results in the knowledge of the distance between v and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location. In a joint work with D. Mazauric, F. Mc Inerney, N. Nisse and S. P ́erennes, we addressed the generalization of the Localization Game where k ≥ 1 vertices can be probed at every step, which also stands as a generalization of the notion of metric dimension of graphs. Precisely, given a graph G and two integers k, l ≥ 1, the Localization problem asks whether there exists a strategy to locate a target hidden in a given graph G in at most l steps and probing at most k vertices per step. The Localization problem is, in general, hard to comprehend. However, we settled it in the context of trees; namely:

• On the negative side, the Localization problem is, in general, NP-complete when restricted to trees.

• On the positive side, there is a (+1)-approximation for the problem in trees, i.e., a polynomial strategy to locate the target in at most one more step than the optimal number of steps.

In other words, in trees, the hardness of the Localization problem only arises from the first probing step, which is NP-hard to decide. A consequence is that we can optimally determine the location of the target, assuming the first probing step is provided e.g. by an oracle. The talk will be dedicated to discussing these aspects.

Vendredi 11 janvier 2019 - TBA - Julien Baste (Universität Ulm, Allemagne).

Vendredi 1 février 2019 - TBA - Antoine Dailly (G-SCOP, Grenoble).

Emplois - Stages


GT Graphes et Optimisation


edit SideBar