11:00
12:00

Timothé Picavet (LaBRI)

Title: Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors

Abstract:

We show that graphs excluding $K_{2,t}$ as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them have an approximation ratio depending on the size of H. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of H. A new key ingredient in the analysis of these distributed algorithms is the use of asymptotic dimension.

The talk will be in English if there is a non-(sufficiently)-French-speaking person in the audience and in French otherwise.

https://algodist.labri.fr/index.php/Main/GT

LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp