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

DOI10.1016/J.ENDM.2015.07.020MaRDI QIDQ324745zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 2061538 (Why is no real title available?)
• scientific article; zbMATH DE number 3453634 (Why is no real title available?)
• $$\{k\}$$-Packing Functions of Graphs
• Limited packings in graphs
• Reducibility among combinatorial problems
• The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• The multiple domination and limited packing problems in graphs

Cited in

(5)

• $$\{k\}$$-Packing Functions of Graphs
• Labelled packing functions in graphs
• On the complexity of the {\(k\)}-packing function problem
• scientific article; zbMATH DE number 759647 (Why is no real title available?)
• 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)