A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
We improve an analysis of algorithm from paper What can be approximated locally? Case study: Dominating Set. We simplify analysis of local algorithm for Minimal Dominating Set Problem in planar graphs. We reduced the gap between the lower bound and the best so far deterministic local algorithm by half, which now comes to 52.
local algorithm dominating set planar graph approximation algorithms distributed algorithm