Hardness results and approximation algorithms of \(k\)-tuple domination in graphs

DOI10.1016/j.ipl.2003.10.004zbMath1178.68682MaRDI QIDQ1029052

Christian Laforest, Ralf Klasing

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.10.004

zbMATH Keywords

combinatorial problems; approximation algorithms; domination problems

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs, Upper bounds for \(\alpha \)-domination parameters, The upper bound on \(k\)-tuple domination numbers of graphs, The \(k\)-tuple domination number revisited, Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem, The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs, Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs, On the \(k\)-tuple domination of de Bruijn and Kautz digraphs, A generalised upper bound for the \(k\)-tuple domination number, MATCHING PROPERTIES IN DOUBLE DOMINATION EDGE CRITICAL GRAPHS

Cites Work

• \(k\)-tuple domination in graphs
• Some APX-completeness results for cubic graphs
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• A threshold of ln n for approximating set cover
• Simple heuristics for unit disk graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item