PostDoc at MPII
http://people.mpi-inf.mpg.de/~samiri/

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The Minimum Dominating Set (MDS) problem is one of the most fundamental and challenging problems in distributed computing. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, there has been much progress on computing local approximations on sparse graphs, and in particular planar graphs.
In this talk we study distributed and deterministic MDS approximation algorithms for graph classes beyond planar graphs. In particular, we show that existing approximation bound for planar graphs can be lifted to bounded genus graphs, and present a local constant-time, constant-factor MDS approximation algorithm. Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments.

Saeed Amiri

--email hidden

passcode not visible

logged in users only

Local algorithm, approximation, dominating sets, graphs

Basic familiarity with graph theory is enough to participate in the talk, such as knowing what is the class of planar graphs.

We will talk on part of the following paper (Preliminary versions appeared in PODC and DISC 2016 and the full version was submitted to a Journal):

https://arxiv.org/abs/1705.09617