Solving the k-center Problem Efficiently with a Dominating Set Algorithm

Abstract

We present a polynomial time heuristic algorithm for the minimum dominating set problem. The algorithm can readily be used for solving the minimum alpha-all-neighbor dominating set problem and the minimum set cover problem. We apply the algorithm in heuristic solving the minimum k-center problem in polynomial time. Using a standard set of 40 test problems we experimentally show that our k-center algorithm performs much better than other well-known heuristics and is competitive with the best known (non-polynomial time) algorithms for solving the k-center problem in terms of average quality and deviation of the results as well as execution time.