hrcak mascot   Srce   HID

Journal of computing and information technology, Vol. 13 No. 3, 2005.

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č

Puni tekst: engleski, pdf (230 KB) str. 225-234 preuzimanja: 2.437* citiraj
APA 6th Edition
Robič, B. i Mihelič, J. (2005). Solving the k-center Problem Efficiently with a Dominating Set Algorithm. Journal of computing and information technology, 13 (3), 225-234. https://doi.org/10.2498/cit.2005.03.05
MLA 8th Edition
Robič, Borut i Jurij Mihelič. "Solving the k-center Problem Efficiently with a Dominating Set Algorithm." Journal of computing and information technology, vol. 13, br. 3, 2005, str. 225-234. https://doi.org/10.2498/cit.2005.03.05. Citirano 01.03.2021.
Chicago 17th Edition
Robič, Borut i Jurij Mihelič. "Solving the k-center Problem Efficiently with a Dominating Set Algorithm." Journal of computing and information technology 13, br. 3 (2005): 225-234. https://doi.org/10.2498/cit.2005.03.05
Harvard
Robič, B., i Mihelič, J. (2005). 'Solving the k-center Problem Efficiently with a Dominating Set Algorithm', Journal of computing and information technology, 13(3), str. 225-234. https://doi.org/10.2498/cit.2005.03.05
Vancouver
Robič B, Mihelič J. Solving the k-center Problem Efficiently with a Dominating Set Algorithm. Journal of computing and information technology [Internet]. 2005 [pristupljeno 01.03.2021.];13(3):225-234. https://doi.org/10.2498/cit.2005.03.05
IEEE
B. Robič i J. Mihelič, "Solving the k-center Problem Efficiently with a Dominating Set Algorithm", Journal of computing and information technology, vol.13, br. 3, str. 225-234, 2005. [Online]. https://doi.org/10.2498/cit.2005.03.05

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.

Hrčak ID: 44689

URI
https://hrcak.srce.hr/44689

Posjeta: 2.727 *