A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs
Sharareh Alipour, Amir Jafari · 2020
In this paper, we present a randomized LOCAL constant approximation factor algorithm for minimum dominating set (MDS) problem and minimum total dominating set (MTDS) problem in graphs. The approximation factor of this algorithm for planar graphs with no 4-cycles is 18 and 9 for MDS and MTDS problems, respectively.