NP-completeness of the \k \-packing function problem in graphs

DOI10.1016/J.ENDM.2015.07.020zbMATH Open1347.05201OpenAlexW2211690038MaRDI QIDQ324745FDOQ324745

Authors: V. Leoni, M. P. Dobson, E. Hinrichsen 

Publication date: 17 October 2016

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

Recommendations

• On the complexity of the {\(k\)}-packing function problem
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs
• $$\{k\}$$-Packing Functions of Graphs
• Labelled packing functions in graphs
• The complexity of generalized clique packing

zbMATH Keywords

dominating setdually chordal graphset packing

Mathematics Subject Classification ID

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) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Reducibility among combinatorial problems
• Title not available (Why is that?)
• 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, \(P_{4}\)-tidy and split graphs
• $$\{k\}$$-Packing Functions of Graphs
• Title not available (Why is that?)

Cited In (5)

• $$\{k\}$$-Packing Functions of Graphs
• Labelled packing functions in graphs
• On the complexity of the {\(k\)}-packing function problem
• Title not available (Why is that?)
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs

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

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