The multiple domination and limited packing problems in graphs

DOI10.1016/j.ipl.2011.09.002zbMath1260.68152OpenAlexW2042334879MaRDI 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 complexitygraph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

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

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

This page was built for publication: The multiple domination and limited packing problems in graphs