A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs.

Sharareh Alipour Amir Jafari

Published in: SPAA (2020)

Keyphrases

dominating set
objective function
optimal solution
computational complexity
np hard
facility location problem
planar graphs
dynamic programming
linear programming
randomized algorithm
connected dominating set
probabilistic model
closed form
lower and upper bounds