On the complexity of \k\-domination and k-tuple domination in graphs

DOI10.1016/J.IPL.2015.01.007MaRDI QIDQ2345849zbMATH OpenOpenAlexFDO

Authors V. Leoni, P. Torres, Gabriela R. Argiroffo

Publication date 21 May 2015

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

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

zbMATH Keywords

\(\{k\}\)-domination\(k\)-tuple dominationchordal graphscomputational complexityplanar graphssplit graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• \(k\)-tuple domination in graphs
• Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
• Complexity of Total {k}-Domination and Related Problems
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• On the complexity of the labeled domination problem in graphs

Cites work

• \(k\)-tuple domination in graphs
• Algorithmic aspect of k-tuple domination in graphs.
• Approximating clique-width and branch-width
• Characterizations of strongly chordal graphs
• Complexity of Total {k}-Domination and Related Problems
• Dominating sets for split and bipartite graphs
• Dominating Sets in Chordal Graphs
• Easy problems for tree-decomposable graphs
• Generalized domination and efficient domination in graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Nordhaus-Gaddum inequalities for domination in graphs
• On integer domination in graphs and Vizing-like problems
• Perfect elimination orderings of chordal powers of graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The multiple domination and limited packing problems in graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Unit disk graphs
• Variations of \(Y\)-dominating functions on graphs

Cited in

(13)

• \(k\)-tuple domination in graphs
• Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
• Grundy dominating sequences and zero forcing sets
• Algorithmic aspect of k-tuple domination in graphs.
• The multiple domination and limited packing problems in graphs
• Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
• On the complexity of the labeled domination problem in graphs
• Complexity of Total {k}-Domination and Related Problems
• Multiple domination
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• On the complexity of \(k\)-step and \(k\)-hop dominating sets in graphs
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Approximation algorithms for double domination number of graphs

This page was built for publication: On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs

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