Limited packing and multiple domination problems: polynomial time reductions

DOI10.1016/J.DAM.2013.10.023zbMATH Open1288.05205OpenAlexW1993251263MaRDI QIDQ2448892FDOQ2448892

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

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

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)

Cites Work

• Limited packings in graphs
• Title not available (Why is that?)
• \(k\)-tuple domination in graphs
• The multiple domination and limited packing problems in graphs
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• Exploring the complexity boundary between coloring and list-coloring
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Polynomial reductions between the limited packing and tuple domination problems in graphs

Cited In (10)

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