NP-completeness of the \(\{k \}\)-packing function problem in graphs

DOI10.1016/J.ENDM.2015.07.020zbMath1347.05201OpenAlexW2211690038MaRDI QIDQ324745

V. Leoni, Erica G. Hinrichsen, Maria Patricia Dobson

Publication date: 17 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.020

zbMATH Keywords

set packingdominating setdually chordal graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

On the complexity of the {k}-packing function problem ⋮ Towards a Polynomial Equivalence Between $$\{k\}$$ -Packing Functions and k-Limited Packings in Graphs

Cites Work

• Limited packings in graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The multiple domination and limited packing problems in graphs
• The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs
• $$\{k\}$$-Packing Functions of Graphs
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: NP-completeness of the \(\{k \}\)-packing function problem in graphs