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…