A Systematic Experimental Comparison of Exact, Greedy, Local Search, Metaheuristic, and Distributed Algorithms for the Minimum Dominating Set Problem
The Minimum Dominating Set (MDS) problem is an NP-hard optimization problem that aims to find the smallest dominating set of nodes encompassing all nodes of a graph. Because it is equivalent to the cluster covering problem, approximate solutions better than the multiplier (1−ε)lnn cannot be obtained in polynomial time...