\(k\)-tuple domination in graphs
From MaRDI portal
Publication:1014390
DOI10.1016/S0020-0190(03)00233-3zbMath1175.68299MaRDI QIDQ1014390
Chung-Shou Liao, Gerard Jennhwa Chang
Publication date: 28 April 2009
Published in: Information Processing Letters (Search for Journal in Brave)
algorithmsbipartite graphsplit graphchordal graphdominationstrongly chordal graph\(k\)-tuple domination
Related Items (56)
The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs ⋮ A polyhedral view to a generalization of multiple domination ⋮ Tuple domination on graphs with the consecutive-zeros property ⋮ \((1, j)\)-set problem in graphs ⋮ On the \(k\)-tuple domination of de Bruijn and Kautz digraphs ⋮ Revisiting \(k\)-tuple dominating sets with emphasis on small values of \(k\) ⋮ Approximating the Spanning k-Tree Forest Problem ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Complexity of edge monitoring on some graph classes ⋮ Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA ⋮ \(k\)-tuple total domination in cross products of graphs ⋮ On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs ⋮ Algorithmic aspects of paired disjunctive domination in graphs ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ The multiple domination and limited packing problems in graphs ⋮ Liar's dominating set problem on unit disk graphs ⋮ On the complexity of the labeled domination problem in graphs ⋮ Algorithmic aspects of \(k\)-tuple total domination in graphs ⋮ Rainbow domination and related problems on strongly chordal graphs ⋮ The upper bound on \(k\)-tuple domination numbers of graphs ⋮ Limited packing and multiple domination problems: polynomial time reductions ⋮ Capacitated Domination Problem ⋮ \(k\)-domination and \(k\)-independence in graphs: A survey ⋮ Upper bounds on the balanced \(\langle \mathbf{r}, \mathbf{s} \rangle\)-domination number of a graph ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Algorithms for generating strongly chordal graphs ⋮ Variations of \(Y\)-dominating functions on graphs ⋮ Restricted domination parameters in graphs ⋮ A generalised upper bound for the \(k\)-tuple domination number ⋮ MATCHING PROPERTIES IN DOUBLE DOMINATION EDGE CRITICAL GRAPHS ⋮ Complexity of distance paired-domination problem in graphs ⋮ Capacitated domination problem ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs ⋮ \(k\)-tuple total domination in graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ Paired versus double domination in \(K_{1,r}\)-free graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs ⋮ Minimum 2-tuple dominating set of permutation graphs ⋮ A note on the \(k\)-tuple total domination number of a graph ⋮ Onk-tuple domination of random graphs ⋮ Multiple Domination ⋮ Double vertex-edge domination in graphs: complexity and algorithms ⋮ Unnamed Item ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs ⋮ Bounds on the k-tuple domatic number of a graph ⋮ Hardness results and approximation algorithms of \(k\)-tuple domination in graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Polynomial reductions between the Limited Packing and Tuple Domination problems in graphs ⋮ Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs ⋮ Liar's domination in graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Upper bounds for the domination numbers of graphs using Turán's theorem and Lovász local lemma ⋮ Generalized limited packings of some graphs with a limited number of \(P_4\)-partners ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs
Cites Work
- Domination, independent domination, and duality in strongly chordal graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- A linear algorithm for the domination number of a tree
- Algorithmic aspect of \(k\)-tuple domination in graphs.
- Nordhaus-Gaddum inequalities for domination in graphs
- Doubly lexical ordering of dense 0--1 matrices
- Characterizations of totally balanced matrices
- Totally-Balanced and Greedy Matrices
- On the Algorithmic Complexity of Total Domination
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Doubly Lexical Orderings of Matrices
- Three Partition Refinement Algorithms
- Edge Dominating Sets in Graphs
- R -Domination in Graphs
- The edge domination problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: \(k\)-tuple domination in graphs
