Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Distributed Dominating Set in Bounded Genus Graphs
Speaker:Saeed Amiri
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:PostDoc at MPII

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

Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 13 February 2018
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Saeed Amiri
EMail:samiri@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Local algorithm, approximation, dominating sets, graphs
Note: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
Attachments, File(s):

Created:
Saeed Amiri, 02/09/2018 10:45 AM
Last modified:
Uwe Brahm/MPII/DE, 02/13/2018 07:01 AM
  • Saeed Amiri, 02/09/2018 10:46 AM
  • Saeed Amiri, 02/09/2018 10:45 AM -- Created document.