Towards a Polynomial Equivalence Between $$\{k\}$$ -Packing Functions and k-Limited Packings in Graphs
DOI10.1007/978-3-319-45587-7_14zbMath1445.68170OpenAlexW2516984173MaRDI QIDQ2835672
V. Leoni, Maria Patricia Dobson
Publication date: 30 November 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-45587-7_14
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- NP-completeness of the \(\{k \}\)-packing function problem in graphs
- The multiple domination and limited packing problems in graphs
- The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs
- On the complexity of the {k}-packing function problem
- $$\{k\}$$-Packing Functions of Graphs
- Limited Packings in Graphs
- Exploring the complexity boundary between coloring and list-coloring
This page was built for publication: Towards a Polynomial Equivalence Between $$\{k\}$$ -Packing Functions and k-Limited Packings in Graphs
