dc.creator | Dobson, Maria Patricia | |
dc.creator | Hinrichsen, Erica Gretel | |
dc.creator | Leoni, Valeria Alejandra | |
dc.date.accessioned | 2018-07-26T19:20:47Z | |
dc.date.available | 2018-07-26T19:20:47Z | |
dc.date.created | 2018-07-26T19:20:47Z | |
dc.date.issued | 2017-01 | |
dc.identifier | Dobson, Maria Patricia; Hinrichsen, Erica Gretel; Leoni, Valeria Alejandra; On the complexity of the {k}-packing function problem; Blackwell Publishers; International Transactions in Operational Research; 24; 1-2; 1-2017; 347-354 | |
dc.identifier | 0969-6016 | |
dc.identifier | http://hdl.handle.net/11336/53214 | |
dc.identifier | CONICET Digital | |
dc.identifier | CONICET | |
dc.description.abstract | Given a positive integer k, the “ {k} -packing function problem” ({k} PF) is to find in a given graph G, a function f that assigns a nonnegative integer to the vertices of G in such a way that the sum of {k} over each closed neighborhood is at most k and over the whole vertex set of G (weight of f) is maximum. It is known that ({k} PF is linear time solvable in strongly chordal graphs and in graphs with clique-width bounded by a constant. In this paper we prove that {k} PF is NP-complete, even when restricted to chordal graphs that constitute a superclass of strongly chordal graphs. To find other subclasses of chordal graphs where {k} PF is tractable, we prove that it is linear time solvable for doubly chordal graphs, by proving that it is so in the superclass of dually chordal graphs, which are graphs that have a maximum neighborhood ordering. | |
dc.language | eng | |
dc.publisher | Blackwell Publishers | |
dc.relation | info:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1111/itor.12276 | |
dc.relation | info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12276 | |
dc.rights | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | |
dc.rights | info:eu-repo/semantics/restrictedAccess | |
dc.subject | Chordal Graph | |
dc.subject | Np-Completeness | |
dc.subject | Polynomial Instances | |
dc.title | On the complexity of the {k}-packing function problem | |
dc.type | info:eu-repo/semantics/article | |
dc.type | info:ar-repo/semantics/artículo | |
dc.type | info:eu-repo/semantics/publishedVersion | |