Towards a polynomial equivalence between \k\-packing functions and k-limited packings in graphs
From MaRDI portal
Publication:2835672
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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
- $$\{k\}$$-Packing Functions of Graphs
- NP-completeness of the \(\{k \}\)-packing function problem in graphs
- On the complexity of the {\(k\)}-packing function problem
- Labelled packing functions in graphs
- The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
Cites work
- $$\{k\}$$-Packing Functions of Graphs
- Exploring the complexity boundary between coloring and list-coloring
- Limited Packings in Graphs
- NP-completeness of the \(\{k \}\)-packing function problem in graphs
- On the complexity of the {\(k\)}-packing function problem
- The \(k\)-limited packing and \(k\)-tuple domination problems in strongly chordal, \(P_{4}\)-tidy and split graphs
- The multiple domination and limited packing problems in graphs
Cited in
(5)
This page was built for publication: Towards a polynomial equivalence between \(\{k\}\)-packing functions and \(k\)-limited packings in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835672)
