Izvorni znanstveni članak
https://doi.org/10.2498/cit.2005.03.05
Solving the k-center Problem Efficiently with a Dominating Set Algorithm
Borut Robič
Jurij Mihelič
Sažetak
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.
Ključne riječi
Hrčak ID:
44689
URI
Datum izdavanja:
30.9.2005.
Posjeta: 3.630 *