Limited packing and multiple domination problems: polynomial time reductions

DOI10.1016/J.DAM.2013.10.023MaRDI QIDQ2448892zbMATH OpenOpenAlexFDO

Authors V. Leoni, G. Nasini

Publication date 5 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.10.023

zbMATH Keywords

computational complexity\(k\)-limited packingpolynomial time reductions\(k\)-tuple dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Polynomial reductions between the limited packing and tuple domination problems in graphs
• The multiple domination and limited packing problems in graphs
• Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• Limited packings in graphs

Cites work

• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Exploring the complexity boundary between coloring and list-coloring
• Limited packings in graphs
• Polynomial reductions between the limited packing and tuple domination problems in graphs
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• The multiple domination and limited packing problems in graphs
• \(k\)-tuple domination in graphs

Cited in

(10)

• Decomposition of Multiple Packings with Subquadratic Union Complexity
• Polynomial reductions between the limited packing and tuple domination problems in graphs
• A polyhedral view to a generalization of multiple domination
• Multiple domination
• More on limited packings in graphs
• A polyhedral view to generalized multiple domination and limited packing
• The multiple domination and limited packing problems in graphs
• On 2-limited packings of complete grid graphs
• Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
• Labelled packing functions in graphs

This page was built for publication: Limited packing and multiple domination problems: polynomial time reductions

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