On the complexity of the {k}-packing function problem

DOI10.1111/ITOR.12276MaRDI QIDQ2968508zbMATH OpenOpenAlexFDO

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

Publication date 16 March 2017

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/itor.12276

zbMATH Keywords

NP-completenesschordal graphpolynomial instances

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 2061538 (Why is no real title available?)
• $$\{k\}$$-Packing Functions of Graphs
• A survey on graphs which have equal domination and closed neighbourhood packing numbers
• Limited packings in graphs
• NP-completeness of the \(\{k \}\)-packing function problem in graphs
• 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

(6)

• Denser packings obtained in \(O(n \log \log n)\) time
• Labelled packing functions in graphs
• scientific article; zbMATH DE number 4089565 (Why is no real title available?)
• Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs
• NP-completeness of the \(\{k \}\)-packing function problem in graphs
• Complexity results for the horizontal bar packing problem

This page was built for publication: On the complexity of the {\(k\)}-packing function problem

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