Heuristics for k-domination models of facility location problems in street networks

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:	Mathematics Computer Science & Informatics
Publisher:	Elsevier
ISSN:	0305-0548
Date of First Compliant Deposit:	12 May 2021
Date of Acceptance:	11 May 2021
Last Modified:	07 Nov 2023 03:13
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