Weighted domination models and randomized heuristics

Dijkstra, Lukas, Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706 and Zverovich, Vadim 2025. Weighted domination models and randomized heuristics. Utilitas Mathematica 123 , pp. 61-86. 10.61091/um123-05

PDF - Published Version Available under License Creative Commons Attribution. Download (698kB)

Abstract

We consider the minimum weight and smallest weight minimum-size dominating set problems in vertex-weighted graphs and networks. The latter problem is a two-objective optimization problem, which is different from the classic minimum weight dominating set problem that requires finding a dominating set of the smallest weight in a graph without trying to optimize its cardinality. In other words, the objective of minimizing the size of the dominating set in the two-objective problem can be considered as a constraint, i.e. a particular case of finding Pareto-optimal solutions. First, we show how to reduce the two-objective optimization problem to the minimum weight dominating set problem by using Integer Linear Programming formulations. Then, under different assumptions, the probabilistic method is applied to obtain upper bounds on the minimum weight dominating sets in graphs. The corresponding randomized algorithms for finding small-weight dominating sets in graphs are described as well. Computational experiments are used to illustrate the results for two different types of random graphs.

Item Type:	Article
Date Type:	Published Online
Status:	Published
Schools:	Schools > Mathematics
ISSN:	0315-3681
Date of First Compliant Deposit:	10 September 2025
Date of Acceptance:	15 June 2025
Last Modified:	11 Sep 2025 09:17
URI:	https://orca.cardiff.ac.uk/id/eprint/181034

Actions (repository staff only)

Edit Item