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

Jurij Mihelič, Borut Robič


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.

Full Text:



Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Crossref Similarity Check logo

Crossref logologo_doaj

 Hrvatski arhiv weba logo