A Local Constant Factor MDS Approximation for Bounded Genus Graphs
Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz · 2016
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs.