Meta-Theorems for Cuttable Distributed Problems

Marthe Bonamy, Avinandan Das, Cyril Gavoille +3

We prove that given any $\alpha$-approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an $f(g)$-round $(3\alpha +1)$-approximation LOCAL algorithm…