Approximation algorithms and ratios for multiple domination in graphs

DOI10.1016/J.DAM.2026.07.021MaRDI QIDQ7353732zbMATH OpenFDO

Authors Lukas Dijkstra, Vadim Zverovich, Andrei Gagarin

Publication date 18 September 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.07.021

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cites work

• \(k\)-tuple domination in graphs
• A generalised upper bound for the k-tuple domination number
• A threshold of ln n for approximating set cover
• Algorithmic aspects of the \(k\)-domination problem in graphs
• Approximation algorithms for combinatorial problems
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Heuristics for \(k\)-domination models of facility location problems in street networks
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Modern applications of graph theory
• New bounds on the \(k\)-domination number and the \(k\)-tuple domination number
• On the approximability and exact algorithms for vector domination and related problems in graphs
• Onk-domination and minimum degree in graphs
• Some APX-completeness results for cubic graphs

This page was built for publication: Approximation algorithms and ratios for multiple domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7353732)