3 papers
math.CO2026
Approximation algorithms and ratios for multiple domination in graphs
Lukas Dijkstra, Vadim Zverovich, Andrei Gagarin
We analyse approximation algorithms (greedy heuristics) for the classical domination number and two multiple domination numbers in simple graphs. First, we present a short self-con…
cs.DM2024
Greedy and randomized heuristics for optimization of k-domination models in digraphs and road networks
Lukas Dijkstra, Andrei Gagarin, Padraig Corcoran +1
Directed graphs provide more subtle and precise modelling tools for optimization in road networks than simple graphs. In particular, they are more suitable in the context of altern…
math.CO2022
Weighted domination models and randomized heuristics
Lukas Dijkstra, Andrei Gagarin, Vadim Zverovich
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 p…