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

• Title not available (Why is that?)
• Title not available (Why is that?)
• $$\{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
• 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)