Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Corcoran, Padraig and Gagarin, Andrei 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
Item availability restricted.

[img] PDF - Accepted Post-Print Version
Restricted to Repository staff only until 25 November 2022 due to copyright restrictions.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB)

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: 14 Jun 2021 10:26
URI: http://orca.cardiff.ac.uk/id/eprint/141210

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics