Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
From MaRDI portal
Publication:1029052
DOI10.1016/j.ipl.2003.10.004zbMath1178.68682OpenAlexW1980243423MaRDI QIDQ1029052
Ralf Klasing, Christian Laforest
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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
A polyhedral view to a generalization of multiple domination ⋮ Hardness Results for Seeding Complex Contagion with Neighborhoods ⋮ Upper bounds for \(\alpha \)-domination parameters ⋮ On the \(k\)-tuple domination of de Bruijn and Kautz digraphs ⋮ Heuristics for \(k\)-domination models of facility location problems in street networks ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs ⋮ Algorithmic aspects of paired disjunctive domination in graphs ⋮ Fault-tolerant total domination via submodular function approximation ⋮ On \(k\)-vertex-edge domination of graph ⋮ Liar's dominating set problem on unit disk graphs ⋮ The complexity of secure domination problem in graphs ⋮ On the \((h,k)\)-domination numbers of iterated line digraphs ⋮ Algorithmic aspects of \(k\)-tuple total domination in graphs ⋮ Global total \(k\)-domination: approximation and hardness results ⋮ Rainbow domination and related problems on strongly chordal graphs ⋮ The upper bound on \(k\)-tuple domination numbers of graphs ⋮ \(k\)-domination and \(k\)-independence in graphs: A survey ⋮ Algorithmic aspects of semitotal domination in graphs ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ A generalised upper bound for the \(k\)-tuple domination number ⋮ The \(k\)-tuple domination number revisited ⋮ MATCHING PROPERTIES IN DOUBLE DOMINATION EDGE CRITICAL GRAPHS ⋮ Constant thresholds can make target set selection tractable ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem ⋮ The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs ⋮ Complexity and algorithms for semipaired domination in graphs ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ Multiple Domination ⋮ Double vertex-edge domination in graphs: complexity and algorithms ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ Bounds on the k-tuple domatic number of a graph ⋮ Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs ⋮ Upper bounds for the domination numbers of graphs using Turán's theorem and Lovász local lemma ⋮ CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS
Cites Work
