Corcoran, Padraig  ORCID: https://orcid.org/0000-0001-9731-3385 and Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706
2021.
Heuristics for k-domination models of facility location problems in street networks.
Computers and Operations Research
133
, 105368.
10.1016/j.cor.2021.105368
|
Preview |
PDF
- Accepted Post-Print Version
Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview |
Abstract
We present new greedy and beam search heuristic methods to find small-size k-dominating sets in graphs. The methods are inspired by a new problem formulation which explicitly highlights a certain structure of the problem. An empirical evaluation of the new methods is done with respect to two existing methods, using instances of graphs corresponding to street networks. The k-domination problem with respect to this class of graphs can be used to model real-world facility location problem scenarios. For the classic minimum dominating set (1-domination) problem, all except one methods perform similarly, which is due to their equivalence in this particular case. However, for the k-domination problem with k>1, the new methods outperform the benchmark methods, and the performance gain is more significant for larger values of k.
| Item Type: | Article |
|---|---|
| Date Type: | Publication |
| Status: | Published |
| Schools: | Schools > Mathematics Schools > Computer Science & Informatics |
| Publisher: | Elsevier |
| ISSN: | 0305-0548 |
| Date of First Compliant Deposit: | 12 May 2021 |
| Date of Acceptance: | 11 May 2021 |
| Last Modified: | 28 Nov 2024 08:45 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/141210 |
Citation Data
Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Dimensions
Dimensions