The multiple domination and limited packing problems in graphs

DOI10.1016/j.ipl.2011.09.002zbMath1260.68152MaRDI QIDQ1944215

V. Leoni, Maria Patricia Dobson, Graciela L. Nasini

Publication date: 4 April 2013

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

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

zbMATH Keywords

computational complexity; graph algorithms

Mathematics Subject Classification ID

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

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

NP-completeness of the \(\{k \}\)-packing function problem in graphs, On 2-limited packings of complete grid graphs, More on limited packings in graphs, A polyhedral view to a generalization of multiple domination, Labelled packing functions in graphs, Tuple domination on graphs with the consecutive-zeros property, The probabilistic approach to limited packings in graphs, 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, Limited packing and multiple domination problems: polynomial time reductions, Towards a Polynomial Equivalence Between $$\{k\}$$ -Packing Functions and k-Limited Packings in Graphs, On the complexity of the {k}-packing function problem, On the complexity of the labeled domination problem in graphs, Multiple Domination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Weakly triangulated graphs
• Limited packings in graphs
• \(k\)-tuple domination in graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Balanced matrices
• The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs
• Characterizations of totally balanced matrices
• A New Class of Brittle Graphs
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Recognizing $P_4 $-Sparse Graphs in Linear Time