Weighted domination models and randomized heuristics
From MaRDI portal
Publication:6505536
arXiv2203.00799MaRDI QIDQ6505536FDOQ6505536
Lukas Dijkstra, Vadim Zverovich, Andrei Gagarin
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. 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 developed 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.
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Stochastic network models in operations research (90B15)
This page was built for publication: Weighted domination models and randomized heuristics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505536)
