Mostrar el registro sencillo del ítem
dc.contributor.author
Leoni, Valeria Alejandra
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Dobson, Maria Patricia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2018-07-20T16:12:21Z
dc.date.issued
2016-05
dc.identifier.citation
Leoni, Valeria Alejandra; Dobson, Maria Patricia; Towards a polynomial equivalence between {k}-packing functions and k-limited packings in graphs; Springer; Lecture Notes in Computer Science; 9849; 5-2016; 160-165
dc.identifier.issn
0302-9743
dc.identifier.uri
http://hdl.handle.net/11336/52744
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 of maximum weight that assigns a non-negative integer to the vertices of G in such a way that the sum of f(v) over each closed neighborhood is at most k. This notion was recently introduced as a variation of the k-limited packing problem (kLP) introduced in 2010, where the function was supposed to assign a value in {0, 1}. For all the graph classes explored up to now, {k}PF and kLP have the same computational complexity. It is an open problem to determine a graph class where one of them is NP-complete and the other, polynomially solvable. In this work, we first prove that {k}PF is NP-complete for bipartite graphs, as kLP is known to be. We also obtain new graph classes where the complexity of these problems would coincide.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Springer
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
Bipartite Graph
dc.subject
Computational Complexity
dc.subject
F-Free Graph
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Towards a polynomial equivalence between {k}-packing functions and k-limited packings in graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2018-07-18T20:50:20Z
dc.journal.volume
9849
dc.journal.pagination
160-165
dc.journal.pais
Suiza
dc.journal.ciudad
Basilea
dc.description.fil
Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina
dc.description.fil
Fil: Dobson, Maria Patricia. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina
dc.journal.title
Lecture Notes in Computer Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/chapter/10.1007%2F978-3-319-45587-7_14
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1007/978-3-319-45587-7_14
Archivos asociados